{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Strong Pair XOR II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #trie #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #字典树 #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumStrongPairXor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出强数对的最大异或值 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 。如果一对整数 <code>x</code> 和 <code>y</code> 满足以下条件，则称其为 <strong>强数对</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>|x - y| &lt;= min(x, y)</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>你需要从 <code>nums</code> 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（<code>XOR</code>）值是在该数组所有强数对中的<strong> 最大值 </strong>。</p>\n",
    "\n",
    "<p>返回数组 <code>nums</code> 所有可能的强数对中的<strong> 最大 </strong>异或值。</p>\n",
    "\n",
    "<p><strong>注意</strong>，你可以选择同一个整数两次来形成一个强数对。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4,5]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>数组<code> nums </code>中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。\n",
    "这些强数对中的最大异或值是 3 XOR 4 = 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [10,100]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>数组<code> nums </code>中有 2 个强数对：(10, 10) 和 (100, 100) 。\n",
    "这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [500,520,2500,3000]\n",
    "<strong>输出：</strong>1020\n",
    "<strong>解释：</strong>数组<code> nums </code>中有 6 个强数对：(500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) 和 (3000, 3000) 。\n",
    "这些强数对中的最大异或值是 500 XOR 520 = 1020 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 2500 XOR 3000 = 636 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 2<sup>20</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-strong-pair-xor-ii](https://leetcode.cn/problems/maximum-strong-pair-xor-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-strong-pair-xor-ii](https://leetcode.cn/problems/maximum-strong-pair-xor-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[10,100]', '[500,520,2500,3000]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        max_bitwise_value = 0\n",
    "        for i in range(N):\n",
    "            for j in range(i, N):\n",
    "                # strong pair\n",
    "                if abs(nums[i]-nums[j])<=min(nums[i], nums[j]):\n",
    "                    # bitwise xor\n",
    "                    xor_value = nums[i]^nums[j]\n",
    "                    max_bitwise_value = max(max_bitwise_value, xor_value)\n",
    "        return max_bitwise_value\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i, n):\n",
    "                y = nums[j]\n",
    "                if abs(x - y) <= min(x, y):\n",
    "                    res = max(res, x ^ y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l=[]\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if abs(nums[i]-nums[j])<=min(nums[i],nums[j]):\n",
    "                    l.append(nums[i]^nums[j])\n",
    "        if l==[]:return 0\n",
    "\n",
    "        return max(l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if abs(nums[i]-nums[j])<=min(nums[i],nums[j]):\n",
    "                    ans=max(ans,nums[i]^nums[j])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "1. 哈希表\n",
    "2x >= y\n",
    "421题\n",
    "\n",
    "2. 0-1 trie\n",
    "更灵活的数据结构\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        # x 越大越好\n",
    "        nums.sort()\n",
    "        ans = mask = 0\n",
    "        high_bit = nums[-1].bit_length() - 1\n",
    "        for i in range(high_bit, -1, -1):\n",
    "            mask |= 1 << i\n",
    "            new_ans = ans | (1 << i)\n",
    "            d = dict()\n",
    "            for y in nums:\n",
    "                mask_y = y & mask\n",
    "                if new_ans ^ mask_y in d and d[new_ans ^ mask_y] * 2 >= y:\n",
    "                    ans = new_ans\n",
    "                    break\n",
    "                d[mask_y] = y # 如果mask_y一样，取谁？\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Item:\n",
    "    __slots__ = (\"h\", )\n",
    "\n",
    "    def __init__(self, h) -> None:\n",
    "        self.h = h\n",
    "\n",
    "    def __gt__(self, rhs: int):\n",
    "        return (rhs >> self.h & 1) == 0\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        high = nums[-1].bit_length()\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        r = 0\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            while r < n and (nums[r] <= x * 2):\n",
    "                r += 1\n",
    "            while l < n and (nums[l] < (x + 1 >> 1)):\n",
    "                l += 1\n",
    "            L, R = l, r\n",
    "            for h in range(high - 1, -1, -1):\n",
    "                M = bisect_left(nums, Item(h), L, R)\n",
    "                if x >> h & 1:\n",
    "                    if L < M:\n",
    "                        R = M\n",
    "                    else:\n",
    "                        L = M\n",
    "                else:\n",
    "                    if M < R:\n",
    "                        L = M\n",
    "                    else:\n",
    "                        R = M\n",
    "            ans = max(ans, x ^ nums[L])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ret = 0\n",
    "        for i in range(len(nums)):\n",
    "            x = nums[i]\n",
    "            r = i\n",
    "            l = bisect.bisect_left(nums, (x + 1) // 2)\n",
    "            m = -1\n",
    "            for k in range(20, -1, -1):\n",
    "                if x & (1 << k) > 0:\n",
    "                    m = k\n",
    "                    break\n",
    "            now = 0\n",
    "            for k in range(m, -1, -1):\n",
    "                s = 1 << k\n",
    "                if x & s > 0:\n",
    "                    rr = bisect.bisect_left(nums, now + s, l, r + 1) - 1\n",
    "                    if rr >= l:\n",
    "                        r = rr\n",
    "                    else:\n",
    "                        now += s\n",
    "                else:\n",
    "                    ll = bisect.bisect_left(nums, now + s, l, r + 1)\n",
    "                    if ll <= r:\n",
    "                        l = ll\n",
    "                        now += s\n",
    "            ret = max(x ^ now, ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        d, ans = [[] for i in range(max(nums).bit_length() + 1)], 0\n",
    "        for x in nums:\n",
    "            d[x.bit_length()].append(x)\n",
    "        d[-1].sort()\n",
    "        while len(d) >= 2:\n",
    "            a, a1 = d.pop(), d[-1]\n",
    "            a1.sort()\n",
    "            if not a:\n",
    "                continue\n",
    "            n = len(d) - 1\n",
    "            if a1 and a1[-1] * 2 >= a[0]:\n",
    "                a.append(inf)\n",
    "                mask = 1 << n\n",
    "                for i in range(n - 1, -1, -1):\n",
    "                    s, j = set(), 0\n",
    "                    mask |= 1 << i\n",
    "                    for x in a1:\n",
    "                        x2 = x * 2\n",
    "                        while a[j] <= x2:\n",
    "                            s.add(a[j] & mask)\n",
    "                            j += 1\n",
    "                        if x & mask ^ mask in s:\n",
    "                            break\n",
    "                    else:\n",
    "                        mask ^= 1 << i\n",
    "                ans = max(ans, mask)\n",
    "            if ans.bit_length() > n :\n",
    "                break\n",
    "            mask = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                s = set()\n",
    "                mask |= 1 << i\n",
    "                for x in a:\n",
    "                    x &= mask\n",
    "                    if x ^ mask in s:\n",
    "                        break\n",
    "                    s.add(x)\n",
    "                else:\n",
    "                    mask ^= 1 << i\n",
    "            ans = max(ans, mask)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans=mask=0\n",
    "        hight_bit=max(nums).bit_length()-1\n",
    "        for i in range(hight_bit,-1,-1):\n",
    "            mask|=1<<i\n",
    "            new_ans=ans|1<<i\n",
    "            seen={}\n",
    "            for x in nums:\n",
    "                xm=x&mask\n",
    "\n",
    "                if (xm^new_ans in seen) and (2*seen[xm^new_ans]>=x):\n",
    "                    ans=new_ans\n",
    "                    break\n",
    "                seen[xm]=x\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans, mask = 0, 0 \n",
    "        high_bit = max(nums).bit_length() - 1\n",
    "        seen = dict()\n",
    "        for i in range(high_bit, -1, -1) : \n",
    "            mask |= 1 << i \n",
    "            new_ans = ans | (1 << i)\n",
    "            seen.clear()\n",
    "            for x in nums : \n",
    "                mask_x = mask & x \n",
    "                if new_ans ^ mask_x in seen and seen[new_ans ^ mask_x] * 2 >= x : \n",
    "                    ans = new_ans\n",
    "                    break \n",
    "                seen[mask_x] = x  \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = nums[-1].bit_length()\n",
    "        res = mask = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            mask |= 1 << i\n",
    "            s, tmp, mp = set(), res | (1 << i), {}\n",
    "            for i, x in enumerate(nums): # a ^ x = tmp, a = x ^ tmp\n",
    "                x &= mask\n",
    "                a = x ^ tmp\n",
    "                if a in s and nums[i] <= nums[mp[a]] * 2:\n",
    "                    res = tmp  \n",
    "                    break\n",
    "                s.add(x)\n",
    "                mp[x] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(20, -1, -1):\n",
    "            res <<= 1\n",
    "            mn_pref, mx_pref = {}, {}\n",
    "            for num in nums:\n",
    "                p = num >> i\n",
    "                if p not in mn_pref:\n",
    "                    mn_pref[p] = mx_pref[p] = num\n",
    "                if mn_pref[p] > num:\n",
    "                    mn_pref[p] = num\n",
    "                if mx_pref[p] < num:\n",
    "                    mx_pref[p] = num\n",
    "            for x in mn_pref:\n",
    "                y = res ^ 1 ^ x\n",
    "                if x >= y and y in mn_pref and mn_pref[x] <= mx_pref[y] * 2:\n",
    "                    res |= 1\n",
    "                    break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        HIGH_BIT = 21\n",
    "        x = 0\n",
    "        for k in range(HIGH_BIT, -1, -1):\n",
    "            seen = defaultdict(int)\n",
    "            left = 0\n",
    "\n",
    "            x_next = x * 2 + 1\n",
    "            found = False\n",
    "            \n",
    "            for i in range(len(nums)):\n",
    "                while nums[i] - nums[left] > nums[left]:\n",
    "                    seen[nums[left] >> k] -= 1\n",
    "                    left += 1\n",
    "                if seen[x_next ^ (nums[i] >> k)] > 0:\n",
    "                    found = True\n",
    "                    break\n",
    "                seen[nums[i] >> k] += 1\n",
    "\n",
    "            if found:\n",
    "                x = x_next\n",
    "            else:\n",
    "                x = x_next - 1\n",
    "        \n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = mask = 0\n",
    "        hbit = max(nums).bit_length() - 1\n",
    "        for j in range(hbit, -1, -1):\n",
    "            \n",
    "            mask |= 1 << j\n",
    "            new_ans = ans | (1 << j)\n",
    "            # print(new_ans)\n",
    "            q = deque([])\n",
    "            # seem = set()\n",
    "            d = defaultdict(int)\n",
    "            b = [(x & mask) for x in nums]\n",
    "            # print(b)\n",
    "            for i in range(n):\n",
    "                x = b[i]\n",
    "                while len(q) > 0:\n",
    "                    t = q.popleft()\n",
    "                    if nums[t] * 2 < nums[i]:\n",
    "                        d[b[t]] -= 1\n",
    "                        # if b[t] in seem:\n",
    "                        #     seem.remove(b[t])\n",
    "                    else:\n",
    "                        q.appendleft(t)\n",
    "                        break\n",
    "                # print(j, new_ans ^ x, seem)\n",
    "                if d[new_ans ^ x] > 0:\n",
    "                    ans = new_ans\n",
    "                    break\n",
    "                d[x] += 1\n",
    "                # seem.add(x)\n",
    "                q.append(i)\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "    def __init__(self, max_bit: int = 30):\n",
    "        self.inf = 1 << 63\n",
    "        self.to = [[-1], [-1]]\n",
    "        self.cnt = [0]\n",
    "        self.max_bit = max_bit\n",
    "\n",
    "    def add(self, num: int) -> None:\n",
    "        cur = 0\n",
    "        self.cnt[cur] += 1\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            if self.to[bit][cur] == -1:\n",
    "                self.to[bit][cur] = len(self.cnt)\n",
    "                self.to[0].append(-1)\n",
    "                self.to[1].append(-1)\n",
    "                self.cnt.append(0)\n",
    "            cur = self.to[bit][cur]\n",
    "            self.cnt[cur] += 1\n",
    "        return\n",
    "\n",
    "    def remove(self, num: int) -> bool:\n",
    "        if self.cnt[0] == 0:\n",
    "            return False\n",
    "        cur = 0\n",
    "        rm = [0]\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0:\n",
    "                return False\n",
    "            rm.append(cur)\n",
    "        for cur in rm:\n",
    "            self.cnt[cur] -= 1\n",
    "        return True\n",
    "\n",
    "    def count(self, num: int):\n",
    "        cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0:\n",
    "                return 0\n",
    "        return self.cnt[cur]\n",
    "\n",
    "    # Get max result for constant x ^ element in array\n",
    "    def max_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0:\n",
    "            return -self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit ^ 1][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                cur = self.to[bit][cur]\n",
    "            else:\n",
    "                res |= 1 << k\n",
    "                cur = nxt\n",
    "\n",
    "        return res\n",
    "\n",
    "    # Get min result for constant x ^ element in array\n",
    "    def min_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0:\n",
    "            return self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                res |= 1 << k\n",
    "                cur = self.to[bit ^ 1][cur]\n",
    "            else:\n",
    "                cur = nxt\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        t = BinaryTrie(22)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l,r = 0,0 \n",
    "        ans = 0\n",
    "        while l < n:\n",
    "            while r < n and nums[r] <= 2 * nums[l]:\n",
    "                t.add(nums[r])\n",
    "                r += 1\n",
    "            ans = max(ans, t.max_xor(nums[l]))\n",
    "            t.remove(nums[l])\n",
    "            l += 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "    def __init__(self, max_bit: int = 30):\n",
    "        self.inf = 1 << 63\n",
    "        self.to = [[-1], [-1]]\n",
    "        self.cnt = [0]\n",
    "        self.max_bit = max_bit\n",
    "\n",
    "    def add(self, num: int) -> None:\n",
    "        cur = 0\n",
    "        self.cnt[cur] += 1\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            if self.to[bit][cur] == -1:\n",
    "                self.to[bit][cur] = len(self.cnt)\n",
    "                self.to[0].append(-1)\n",
    "                self.to[1].append(-1)\n",
    "                self.cnt.append(0)\n",
    "            cur = self.to[bit][cur]\n",
    "            self.cnt[cur] += 1\n",
    "        return\n",
    "\n",
    "    def remove(self, num: int) -> bool:\n",
    "        if self.cnt[0] == 0:\n",
    "            return False\n",
    "        cur = 0\n",
    "        rm = [0]\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0:\n",
    "                return False\n",
    "            rm.append(cur)\n",
    "        for cur in rm:\n",
    "            self.cnt[cur] -= 1\n",
    "        return True\n",
    "\n",
    "    def count(self, num: int):\n",
    "        cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0:\n",
    "                return 0\n",
    "        return self.cnt[cur]\n",
    "\n",
    "    # Get max result for constant x ^ element in array\n",
    "    def max_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0:\n",
    "            return -self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit ^ 1][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                cur = self.to[bit][cur]\n",
    "            else:\n",
    "                res |= 1 << k\n",
    "                cur = nxt\n",
    "\n",
    "        return res\n",
    "\n",
    "    # Get min result for constant x ^ element in array\n",
    "    def min_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0:\n",
    "            return self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                res |= 1 << k\n",
    "                cur = self.to[bit ^ 1][cur]\n",
    "            else:\n",
    "                cur = nxt\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        t = BinaryTrie()\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l,r = 0,0 \n",
    "        ans = 0\n",
    "        while l < n:\n",
    "            while r < n and nums[r] <= 2 * nums[l]:\n",
    "                t.add(nums[r])\n",
    "                r += 1\n",
    "            ans = max(ans, t.max_xor(nums[l]))\n",
    "            t.remove(nums[l])\n",
    "            l += 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        return int(max(map(lambda enum: (nums[np.searchsorted(nums, enum[1] + 1 >> 1):enum[0] + 1] ^ enum[1]).max(), enumerate(nums:=np.unique(nums)))))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "    def __init__(self, max_bit: int = 30):\n",
    "        self.inf = 1 << 63\n",
    "        self.to = [[-1], [-1]]\n",
    "        self.cnt = [0]\n",
    "        self.max_bit = max_bit\n",
    "\n",
    "    def add(self, num: int) -> None:\n",
    "        cur = 0\n",
    "        self.cnt[cur] += 1\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            if self.to[bit][cur] == -1:\n",
    "                self.to[bit][cur] = len(self.cnt)\n",
    "                self.to[0].append(-1)\n",
    "                self.to[1].append(-1)\n",
    "                self.cnt.append(0)\n",
    "            cur = self.to[bit][cur]\n",
    "            self.cnt[cur] += 1\n",
    "        return\n",
    "\n",
    "    def remove(self, num: int) -> bool:\n",
    "        if self.cnt[0] == 0:\n",
    "            return False\n",
    "        cur = 0\n",
    "        rm = [0]\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0:\n",
    "                return False\n",
    "            rm.append(cur)\n",
    "        for cur in rm:\n",
    "            self.cnt[cur] -= 1\n",
    "        return True\n",
    "\n",
    "    def count(self, num: int):\n",
    "        cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (num >> k) & 1\n",
    "            cur = self.to[bit][cur]\n",
    "            if cur == -1 or self.cnt[cur] == 0:\n",
    "                return 0\n",
    "        return self.cnt[cur]\n",
    "\n",
    "    # Get max result for constant x ^ element in array\n",
    "    def max_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0:\n",
    "            return -self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit ^ 1][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                cur = self.to[bit][cur]\n",
    "            else:\n",
    "                res |= 1 << k\n",
    "                cur = nxt\n",
    "\n",
    "        return res\n",
    "\n",
    "    # Get min result for constant x ^ element in array\n",
    "    def min_xor(self, x: int) -> int:\n",
    "        if self.cnt[0] == 0:\n",
    "            return self.inf\n",
    "        res = cur = 0\n",
    "        for k in range(self.max_bit, -1, -1):\n",
    "            bit = (x >> k) & 1\n",
    "            nxt = self.to[bit][cur]\n",
    "            if nxt == -1 or self.cnt[nxt] == 0:\n",
    "                res |= 1 << k\n",
    "                cur = self.to[bit ^ 1][cur]\n",
    "            else:\n",
    "                cur = nxt\n",
    "        return res\n",
    "\n",
    "_max = lambda x,y: x if x>=y else y\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        t = BinaryTrie(22)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l,r = 0,0 \n",
    "        ans = 0\n",
    "        while l < n:\n",
    "            while r < n and nums[r] <= 2 * nums[l]:\n",
    "                t.add(nums[r])\n",
    "                r += 1\n",
    "            ans = _max(ans, t.max_xor(nums[l]))\n",
    "            t.remove(nums[l])\n",
    "            l += 1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        count = [{} for _ in range(22)]\n",
    "        ret = 0\n",
    "        n = len(nums)\n",
    "        def insert(v):\n",
    "            topk = 0\n",
    "            for k in range(21,-1,-1):\n",
    "                topk = topk | (v & (1<<k))\n",
    "                if topk not in count[k]:\n",
    "                    count[k][topk] = 1\n",
    "                else:\n",
    "                    count[k][topk] += 1\n",
    "        def delete(v):\n",
    "            topk = 0\n",
    "            for k in range(21,-1,-1):\n",
    "                topk = topk | (v & (1<<k))\n",
    "                count[k][topk] -= 1\n",
    "        \n",
    "        left = -1\n",
    "        right = -1\n",
    "        '''insert(nums[0])\n",
    "        while right + 1 < n and nums[right+1] <= 2 * nums[0]:\n",
    "            right += 1\n",
    "            insert(nums[right])'''\n",
    "        \n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            \n",
    "            while left < i:\n",
    "                if left >= 0:\n",
    "                    delete(nums[left])\n",
    "                left += 1\n",
    "            while right + 1 < n and nums[right+1] <= 2 * x:\n",
    "                right += 1\n",
    "                insert(nums[right])\n",
    "            #print(left,right)\n",
    "\n",
    "            #print(left, right,nums)                \n",
    "                \n",
    "            topk = 0\n",
    "            for k in range(21,-1,-1):\n",
    "                maxv = -1\n",
    "                maxt = -1\n",
    "                for t in range(2):\n",
    "                    topk_t = topk + (t << k)\n",
    "                    if (count[k].get(topk_t,0) > 0) and ((x ^ (t<<k)) & (t<<k) > maxv):\n",
    "                        maxv = (x ^ (t<<k)) & (t<<k)\n",
    "                        maxt = t\n",
    "                topk += maxt<<k\n",
    "                #print(topk, nums)\n",
    "            ret = max(ret, x ^ topk)\n",
    "        return ret\n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "带删除功能的字典树1\n",
    "'''\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        Trie = [None, 0, None, 0]\n",
    "        high = 20\n",
    "\n",
    "        def insert(num):\n",
    "            cur = Trie\n",
    "            i = high\n",
    "            while i >= 0:\n",
    "                j = (num >> i) & 1\n",
    "                if j == 0:\n",
    "                    cur[1] += 1\n",
    "                else:\n",
    "                    cur[-1] += 1\n",
    "                if cur[j << 1] == None:\n",
    "                    cur[j << 1] = [None, 0, None, 0]\n",
    "                cur = cur[j << 1]   \n",
    "                i -= 1             \n",
    "\n",
    "        def remove(num):\n",
    "            cur = Trie\n",
    "            i = high\n",
    "            while i >= 0:\n",
    "                j = (num >> i) & 1\n",
    "                if j == 0:\n",
    "                    cur[1] -= 1\n",
    "                else:\n",
    "                    cur[-1] -= 1\n",
    "\n",
    "                cur = cur[j << 1]\n",
    "                i -= 1        \n",
    "\n",
    "\n",
    "        def find(num):\n",
    "            cur = Trie\n",
    "            i = high\n",
    "            ans = 0\n",
    "            while i >= 0:\n",
    "                j = (num >> i) & 1\n",
    "                if j == 0:\n",
    "                    if cur[-1] > 0:\n",
    "                        ans |= 1 << i\n",
    "                        cur = cur[2]\n",
    "                    else:\n",
    "                        cur = cur[0]   \n",
    "                else:\n",
    "                    if cur[1] > 0:\n",
    "                        cur = cur[0]\n",
    "                        ans |= 1 << i\n",
    "                    else:\n",
    "                        cur = cur[2]\n",
    "                i -= 1   \n",
    "\n",
    "            return ans\n",
    "\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        for y in nums:\n",
    "            insert(y)\n",
    "            while nums[i] * 2 < y:\n",
    "                remove(nums[i])\n",
    "                i += 1\n",
    "            ans = max(ans, find(y))\n",
    "            \n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tire:\n",
    "    __slots__ = \"child\", \"cnt\"\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        self.child = [None, None]\n",
    "        self.cnt = 0\n",
    "\n",
    "    def insert(self, x) -> None:\n",
    "        t = self\n",
    "        for i in range(20, -1, -1):\n",
    "            c = ((x >> i) & 1)\n",
    "            if not t.child[c]:\n",
    "                t.child[c] = Tire()\n",
    "            t.child[c].cnt += 1\n",
    "            t = t.child[c]\n",
    "    \n",
    "    def query(self, x) -> int:\n",
    "        res = 0\n",
    "        t = self\n",
    "        for i in range(20, -1, -1):\n",
    "            c = ((x >> i) & 1)\n",
    "            p = c ^ 1 if t.child[c ^ 1] else c\n",
    "            res |= (c ^ p) << i\n",
    "            t = t.child[p]\n",
    "        return res\n",
    "\n",
    "    def remove(self, x):\n",
    "        stk = []\n",
    "        t = self\n",
    "        for i in range(20, -1, -1):\n",
    "            c = ((x >> i) & 1)\n",
    "            stk.append((t, c))\n",
    "            t = t.child[c]\n",
    "        while stk:\n",
    "            tree, i = stk.pop()\n",
    "            tree.child[i].cnt -= 1\n",
    "            if tree.child[i].cnt == 0:\n",
    "                tree.child[i] = None\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int: \n",
    "        \"\"\"\n",
    "            y - x <= x\n",
    "            y <= 2x\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        tire = Tire()\n",
    "        l = 0\n",
    "        for r, y in enumerate(nums):\n",
    "            tire.insert(y)\n",
    "            while y > 2 * nums[l]:\n",
    "                tire.remove(nums[l])\n",
    "                l += 1\n",
    "            res = max(res, tire.query(y))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    HIGH_BIT = 20\n",
    "    __slots__ = 'son', 'cnt'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.son: List[Trie | None] = [None, None]\n",
    "        self.cnt = 0\n",
    "\n",
    "    def insert(self, num: int) -> None:\n",
    "        node = self\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            j = num >> i & 1\n",
    "            if node.son[j] is None:\n",
    "                node.son[j] = Trie()\n",
    "            node = node.son[j]\n",
    "            node.cnt += 1\n",
    "\n",
    "    def query(self, num: int) -> int:\n",
    "        node, ans = self, 0\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            j = num >> i & 1\n",
    "            if node.son[1 - j]:\n",
    "                ans |= 1 << i\n",
    "                node = node.son[1 - j]\n",
    "            else:\n",
    "                node = node.son[j]\n",
    "        return ans\n",
    "    \n",
    "    def remove(self, num: int) -> None:\n",
    "        node = self\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            j = num >> i & 1\n",
    "            node.son[j].cnt -= 1\n",
    "            if node.son[j].cnt <= 0:\n",
    "                node.son[j] = None\n",
    "                break\n",
    "            node = node.son[j]\n",
    "    \n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        trie = Trie()\n",
    "        nums = sorted(list(set(nums)))\n",
    "        i = j = 0\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            trie.insert(nums[i])\n",
    "            while j < n and nums[j] * 2 < nums[i]:\n",
    "                trie.remove(nums[j])\n",
    "                j += 1\n",
    "            ans = max(ans, trie.query(nums[i]))\n",
    "            i += 1\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'children', 'Pass', 'End'\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.Pass = 0  # 子树大小\n",
    "\n",
    "class Trie:\n",
    "    HIGH_BIT = 19\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    # 添加 val\n",
    "    def insert(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        cur.Pass += 1\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            cur.Pass += 1  # 维护子树大小\n",
    "\n",
    "    # 删除 val，但不删除节点\n",
    "    # 要求 val 必须在 trie 中\n",
    "    def remove(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        cur.Pass -= 1\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            if cur.children[(val >> i) & 1].Pass == 1:\n",
    "                cur.children[(val >> i) & 1] = None\n",
    "                return\n",
    "            cur = cur.children[(val >> i) & 1]\n",
    "            cur.Pass -= 1  # 维护子树大小\n",
    "\n",
    "\n",
    "    # 返回 val 与 trie 中一个元素的最大异或和\n",
    "    # 要求 trie 中至少有一个元素\n",
    "    def max_xor(self, val: int) -> int:\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            # 如果 cur.children[bit^1].Pass == 0，视作空节点\n",
    "            if cur.children[bit ^ 1] and cur.children[bit ^ 1].Pass:\n",
    "                ans |= 1 << i\n",
    "                bit ^= 1\n",
    "            cur = cur.children[bit]\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        t = Trie()\n",
    "        ans = left = 0\n",
    "        for y in nums:\n",
    "            t.insert(y)\n",
    "            while nums[left] * 2 < y:\n",
    "                t.remove(nums[left])\n",
    "                left += 1\n",
    "            ans = max(ans, t.max_xor(y))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        # 1 <= nums.length <= 5 * 104\n",
    "        # 1 <= nums[i] <= 2**20 - 1\n",
    "        N = len(nums)\n",
    "\n",
    "        # 记录每个数二进制\n",
    "        lb = [0] * N\n",
    "\n",
    "        # 记录最高位下标\n",
    "        lm = [[] for _ in range(20)]\n",
    "\n",
    "        # 转换为2进制\n",
    "        def to2(i, n):\n",
    "            l = [0] * 20\n",
    "            b = 0\n",
    "\n",
    "            while n:\n",
    "                n, m = divmod(n, 2)\n",
    "                l[b] = m\n",
    "                b += 1\n",
    "\n",
    "            lb[i] = l\n",
    "            lm[b - 1].append(i)\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            to2(i, n)\n",
    "\n",
    "        # 要求满足|x - y| <= min(x, y)\n",
    "        # 还未满足条件\n",
    "        # l0最高位b，l1最高位b - 1\n",
    "        def calc(b, l0, l1):\n",
    "            if not l0 or not l1:\n",
    "                return -1\n",
    "\n",
    "            if b == 1:\n",
    "                for i in l0:\n",
    "                    if lb[i][0] == 0:\n",
    "                        return 3\n",
    "                return -1\n",
    "\n",
    "            # 按最高位记录下标，全为0记录在-1\n",
    "            lm0 = defaultdict(list)\n",
    "            lm1 = defaultdict(list)\n",
    "\n",
    "            for i in l0:\n",
    "                for _b in range(b - 1, -1, -1):\n",
    "                    if lb[i][_b]:\n",
    "                        lm0[_b].append(i)\n",
    "                        break\n",
    "                else:\n",
    "                    # 全为0\n",
    "                    lm0[-1].append(i)\n",
    "\n",
    "\n",
    "            for i in l1:\n",
    "                for _b in range(b - 2, -1, -1):\n",
    "                    if lb[i][_b]:\n",
    "                        lm1[_b].append(i)\n",
    "                        break\n",
    "                else:\n",
    "                    # 全为0\n",
    "                    lm1[-1].append(i)\n",
    "\n",
    "            ret = -1\n",
    "            add = 2 ** b + 2 ** (b - 1)\n",
    "\n",
    "            # 计算相互间最高位连续\n",
    "            for _b in range(b - 1, 0, -1):\n",
    "                _l0 = lm0[_b]\n",
    "                _l1 = lm1[_b - 1]\n",
    "\n",
    "                v = calc(_b, _l0, _l1)\n",
    "                if v != -1:\n",
    "                    ret = max(ret, add ^ v)\n",
    "\n",
    "            # 计算已经满足条件的\n",
    "            for _b1 in range(b - 2, -2, -1):\n",
    "                for _b0 in range(_b1, -2, -1):\n",
    "                    # 肯定满足条件\n",
    "                    v = calc2(_b1, lm1[_b1], lm0[_b0])\n",
    "                    if v != -1:\n",
    "                        ret = max(ret, add + v)\n",
    "\n",
    "            return ret\n",
    "\n",
    "\n",
    "        # 已经满足条件\n",
    "        # l中元素相互作用\n",
    "        def calc1(b, l):\n",
    "            if len(l) <= 1:\n",
    "                return -1\n",
    "\n",
    "            if b == -1:\n",
    "                return 0\n",
    "\n",
    "            # 分解b位1和0两类\n",
    "            l1 = []\n",
    "            l0 = []\n",
    "\n",
    "            for i in l:\n",
    "                if lb[i][b]:\n",
    "                    l1.append(i)\n",
    "                else:\n",
    "                    l0.append(i)\n",
    "\n",
    "            if l1 and l0:\n",
    "                return 2**b + calc2(b - 1, l1, l0)\n",
    "\n",
    "            return calc1(b - 1, l)\n",
    "\n",
    "        # 已经满足条件\n",
    "        # left和right中元素相互作用\n",
    "        def calc2(b, left, right):\n",
    "            if not left or not right:\n",
    "                return -1\n",
    "\n",
    "            if b == -1:\n",
    "                return 0\n",
    "\n",
    "            # 分解b位1和0两类\n",
    "            l1 = []\n",
    "            l0 = []\n",
    "\n",
    "            for i in left:\n",
    "                if lb[i][b]:\n",
    "                    l1.append(i)\n",
    "                else:\n",
    "                    l0.append(i)\n",
    "\n",
    "            r1 = []\n",
    "            r0 = []\n",
    "\n",
    "            for i in right:\n",
    "                if lb[i][b]:\n",
    "                    r1.append(i)\n",
    "                else:\n",
    "                    r0.append(i)\n",
    "\n",
    "            if l1 and r0:\n",
    "                if l0 and r1:\n",
    "                    ret = calc2(b - 1, l0, r1)\n",
    "                    return 2 ** b + max(ret, calc2(b - 1, l1, r0))\n",
    "                else:\n",
    "                    return 2 ** b + calc2(b - 1, l1, r0)\n",
    "            elif l0 and r1:\n",
    "                return 2 ** b + calc2(b - 1, l0, r1)\n",
    "\n",
    "            return calc2(b - 1, left, right)\n",
    "\n",
    "        ret = 0\n",
    "        for b in range(19, 0, -1):\n",
    "            ret = max(ret, calc1(b - 1, lm[b]))\n",
    "            ret = max(ret, calc(b, lm[b], lm[b - 1]))\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'children', 'cnt'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0\n",
    "\n",
    "class Trie:\n",
    "    HIGH_BIT = 19\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def insert(self, val):\n",
    "        cur = self.root\n",
    "        for k in range(Trie.HIGH_BIT, -1, -1):\n",
    "\n",
    "            bit = (val >> k) & 1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            # 放后面是有必要的\n",
    "            cur.cnt += 1\n",
    "\n",
    "    # 这里是没考虑val不在树中的情况的（题目中也不会出现）\n",
    "    def remove(self, val):\n",
    "        cur = self.root \n",
    "        for k in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> k) & 1\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt -= 1\n",
    "\n",
    "\n",
    "    def search(self, tar_val):\n",
    "        res = 0\n",
    "        cur = self.root\n",
    "        for k in range(Trie.HIGH_BIT, -1, -1):\n",
    "            tarbit = ((tar_val >> k) & 1) ^ 1\n",
    "            if cur.children[tarbit] and cur.children[tarbit].cnt > 0:\n",
    "                res += 1 << k\n",
    "                cur = cur.children[tarbit]\n",
    "            else:\n",
    "                cur = cur.children[tarbit^1]\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = left = 0\n",
    "        tree = Trie()\n",
    "        for y in nums:\n",
    "            tree.insert(y)\n",
    "\n",
    "            while nums[left] * 2 < y:\n",
    "                tree.remove(nums[left])\n",
    "                left += 1\n",
    "            temp = tree.search(y)\n",
    "            ans = max(ans, temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val = -1) -> None:\n",
    "        self.val = val\n",
    "        self.cnt = 1\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.root = Node()\n",
    "\n",
    "    def add(self, x: int, mx: int) -> None:\n",
    "        node = self.root\n",
    "        for i in range(mx - 1, -1, -1):\n",
    "            if (x >> i) & 1 == 0:\n",
    "                if node.left is None:\n",
    "                    node.left = Node(val = 0)\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    node = node.left\n",
    "                    node.cnt += 1\n",
    "            else:\n",
    "                if node.right is None:\n",
    "                    node.right = Node(val = 1)\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node = node.right\n",
    "                    node.cnt += 1\n",
    "\n",
    "    def delete(self, x: int, mx: int) -> None:\n",
    "        node = self.root\n",
    "        for i in range(mx - 1, -1, -1):\n",
    "            if (x >> i) & 1 == 0:\n",
    "                node.left.cnt -= 1\n",
    "                if node.left.cnt == 0:\n",
    "                    node.left = None\n",
    "                    return\n",
    "                node = node.left\n",
    "            else:\n",
    "                node.right.cnt -= 1\n",
    "                if node.right.cnt == 0:\n",
    "                    node.right = None\n",
    "                    return\n",
    "                node = node.right\n",
    "    \n",
    "    def max_xor(self, x: int, mx: int) -> int:\n",
    "        res = 0\n",
    "        node = self.root\n",
    "        for i in range(mx - 1, -1, -1):\n",
    "            if (x >> i) & 1 == 0:\n",
    "                if node.right is not None:\n",
    "                    res |= (1 << i)\n",
    "                    node = node.right\n",
    "                elif node.left is not None:\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    return res\n",
    "            else:\n",
    "                if node.left is not None:\n",
    "                    res |= (1 << i)\n",
    "                    node = node.left\n",
    "                elif node.right is not None:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    return res\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        trie = Trie()\n",
    "        nums.sort()\n",
    "        n = nums[-1].bit_length()\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for y in nums:\n",
    "            while 2 * nums[left] < y:\n",
    "                trie.delete(nums[left], n)\n",
    "                left += 1\n",
    "            ans = max(ans, trie.max_xor(y, n))\n",
    "            trie.add(y, n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class qzs_node:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.is_leaf = False\n",
    "    def add(self, this_idx, val):\n",
    "        if this_idx == 0:\n",
    "            self.is_leaf = True\n",
    "            return \n",
    "        if val // this_idx % 2 == 0:\n",
    "            if self.left == None:\n",
    "                self.left = qzs_node()\n",
    "            self.left.add(this_idx // 2, val)\n",
    "        else:\n",
    "            if self.right == None:\n",
    "                self.right = qzs_node()\n",
    "            self.right.add(this_idx // 2, val)\n",
    "    def del_node(self, this_idx, val):\n",
    "        if this_idx == 0:\n",
    "            return True\n",
    "        if val // this_idx % 2 == 0:\n",
    "            res = self.left.del_node(this_idx // 2, val)\n",
    "            if res:\n",
    "                self.left = None\n",
    "            if res and self.right == None:\n",
    "                return True\n",
    "            return False\n",
    "        else:\n",
    "            res = self.right.del_node(this_idx // 2, val)\n",
    "            if res:\n",
    "                self.right = None\n",
    "            if res and self.left == None:\n",
    "                return True\n",
    "            return False\n",
    "    \n",
    "    def find_max(self, this_idx, val):\n",
    "        if this_idx == 0:\n",
    "            return 0\n",
    "        if self.left == None and self.right == None:\n",
    "            return 0\n",
    "        res = this_idx\n",
    "        if val // this_idx % 2 == 0:\n",
    "            if self.right:\n",
    "                return res + self.right.find_max(this_idx // 2, val)\n",
    "            else:\n",
    "                return self.left.find_max(this_idx // 2, val)\n",
    "        else:\n",
    "            if self.left:\n",
    "                return res + self.left.find_max(this_idx // 2, val)\n",
    "            else:\n",
    "                return self.right.find_max(this_idx // 2, val)\n",
    "        return 0\n",
    "    \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "\n",
    "        val_len = 2 ** 21\n",
    "        arr = sorted(set(nums))\n",
    "        # print(arr)\n",
    "        idx = 0\n",
    "        res = 0\n",
    "        root = qzs_node()\n",
    "        root.add(val_len, arr[0])\n",
    "        for i in range(1, len(arr)):\n",
    "            while arr[idx] * 2 < arr[i]:\n",
    "                root.del_node(val_len, arr[idx])\n",
    "                idx += 1\n",
    "            # print(arr[idx], arr[i], root.left, root.right, root.find_max(val_len, arr[i]))\n",
    "            res = max(res, root.find_max(val_len, arr[i]))\n",
    "            root.add(val_len, arr[i])\n",
    "            \n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "  __slots__ = ['next', 'l', 'r']\n",
    "\n",
    "  def __init__(self):\n",
    "    self.next = [None] * 2\n",
    "    self.l = inf\n",
    "    self.r = -inf\n",
    "\n",
    "  def insert(self, x):\n",
    "    cur = self\n",
    "    for i in range(20, -1, -1):\n",
    "      v = x >> i & 1\n",
    "      if cur.next[v] is None:\n",
    "        cur.next[v] = Trie()\n",
    "      cur = cur.next[v]\n",
    "      cur.l = min(cur.l, x)\n",
    "      cur.r = max(cur.r, x)\n",
    "\n",
    "  def query(self, x, L, R):\n",
    "    cur = self\n",
    "    for i in range(20, -1, -1):\n",
    "      v = x >> i & 1\n",
    "      if cur.next[v ^ 1] and not (cur.next[v ^ 1].r < L or cur.next[v ^ 1].l > R):\n",
    "        cur = cur.next[v ^ 1]\n",
    "      elif cur.next[v] and not (cur.next[v].r < L or cur.next[v].l > R):\n",
    "        cur = cur.next[v]\n",
    "      else:\n",
    "        return 0\n",
    "    return x ^ cur.l\n",
    "\n",
    "class Solution:     \n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "      root = Trie()\n",
    "      ans = 0\n",
    "      for i, v in enumerate(nums):\n",
    "        ans = max(ans, root.query(v, v / 2.0, v * 2))\n",
    "        root.insert(v)\n",
    "\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "XorTrie 最大异或前缀树\n",
    "https://kazuma8128.hatenablog.com/entry/2018/05/06/022654\n",
    "\"\"\"\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class BinaryTrie:\n",
    "    __slots__ = (\n",
    "        \"_maxLog\",\n",
    "        \"_xEnd\",\n",
    "        \"_vList\",\n",
    "        \"_multiset\",\n",
    "        \"_edges\",\n",
    "        \"_size\",\n",
    "        \"_endCount\",\n",
    "        \"_maxV\",\n",
    "        \"_lazy\",\n",
    "    )\n",
    "\n",
    "    def __init__(self, max=1 << 30, addLimit=int(2e5 + 10), allowMultipleElements=True):\n",
    "        \"\"\"\n",
    "        Example:\n",
    "\n",
    "        ```\n",
    "        n = len(nums)\n",
    "        bt = BinaryTrie(max = 1 << 30, addLimit=n, allowMultipleElements=True)\n",
    "        for num in nums:\n",
    "            bt.add(num)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            bt.xor_all(num)\n",
    "            res += bt.bisect_right(high) - bt.bisect_left(low)\n",
    "            bt.xor_all(num)\n",
    "        ```\n",
    "        \"\"\"\n",
    "        maxLog = max.bit_length()\n",
    "        self._maxLog = maxLog\n",
    "        self._xEnd = 1 << maxLog\n",
    "        self._vList = [0] * (maxLog + 1)\n",
    "        self._multiset = allowMultipleElements\n",
    "        n = maxLog * addLimit + 1\n",
    "        self._edges = [-1] * (2 * n)\n",
    "        self._size = [0] * n\n",
    "        self._endCount = [0] * n\n",
    "        self._maxV = 0\n",
    "        self._lazy = 0\n",
    "\n",
    "    def add(self, x: int) -> None:\n",
    "        x ^= self._lazy\n",
    "        v = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            if self._edges[2 * v + d] == -1:\n",
    "                self._maxV += 1\n",
    "                self._edges[2 * v + d] = self._maxV\n",
    "            v = self._edges[2 * v + d]\n",
    "            self._vList[i] = v\n",
    "        if self._multiset or self._endCount[v] == 0:\n",
    "            self._endCount[v] += 1\n",
    "            for v in self._vList:\n",
    "                self._size[v] += 1\n",
    "\n",
    "    def discard(self, x: int) -> None:\n",
    "        if not 0 <= x < self._xEnd:\n",
    "            return\n",
    "        x ^= self._lazy\n",
    "        v = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            if self._edges[2 * v + d] == -1:\n",
    "                return\n",
    "            v = self._edges[2 * v + d]\n",
    "            self._vList[i] = v\n",
    "        if self._endCount[v] > 0:\n",
    "            self._endCount[v] -= 1\n",
    "            for v in self._vList:\n",
    "                self._size[v] -= 1\n",
    "\n",
    "    def erase(self, x: int, count=1):\n",
    "        \"\"\"删除count个x.count=-1表示删除所有x.\"\"\"\n",
    "        if not 0 <= x < self._xEnd:\n",
    "            return\n",
    "        x ^= self._lazy\n",
    "        v = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            if self._edges[2 * v + d] == -1:\n",
    "                return\n",
    "            v = self._edges[2 * v + d]\n",
    "            self._vList[i] = v\n",
    "        if count == -1 or self._endCount[v] < count:\n",
    "            count = self._endCount[v]\n",
    "        if self._endCount[v] > 0:\n",
    "            self._endCount[v] -= count\n",
    "            for v in self._vList:\n",
    "                self._size[v] -= count\n",
    "\n",
    "    def count(self, x: int) -> int:\n",
    "        if not 0 <= x < self._xEnd:\n",
    "            return 0\n",
    "        x ^= self._lazy\n",
    "        v = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            if self._edges[2 * v + d] == -1:\n",
    "                return 0\n",
    "            v = self._edges[2 * v + d]\n",
    "        return self._endCount[v]\n",
    "\n",
    "    def bisectLeft(self, x: int) -> int:\n",
    "        if x < 0:\n",
    "            return 0\n",
    "        if self._xEnd <= x:\n",
    "            return len(self)\n",
    "        v = 0\n",
    "        ret = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            d = (x >> i) & 1\n",
    "            left = (self._lazy >> i) & 1\n",
    "            lc = self._edges[2 * v]\n",
    "            rc = self._edges[2 * v + 1]\n",
    "            if left == 1:\n",
    "                lc, rc = rc, lc\n",
    "            if d:\n",
    "                if lc != -1:\n",
    "                    ret += self._size[lc]\n",
    "                if rc == -1:\n",
    "                    return ret\n",
    "                v = rc\n",
    "            else:\n",
    "                if lc == -1:\n",
    "                    return ret\n",
    "                v = lc\n",
    "        return ret\n",
    "\n",
    "    def bisectRight(self, x: int) -> int:\n",
    "        return self.bisectLeft(x + 1)\n",
    "\n",
    "    def index(self, x: int) -> int:\n",
    "        if x not in self:\n",
    "            raise ValueError(f\"{x} is not in BinaryTrie\")\n",
    "        return self.bisectLeft(x)\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if x not in self:\n",
    "            return -1\n",
    "        return self.bisectLeft(x)\n",
    "\n",
    "    def at(self, index: int) -> int:\n",
    "        if index < 0:\n",
    "            index += self._size[0]\n",
    "        v = 0\n",
    "        ret = 0\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            left = (self._lazy >> i) & 1\n",
    "            lc = self._edges[2 * v]\n",
    "            rc = self._edges[2 * v + 1]\n",
    "            if left == 1:\n",
    "                lc, rc = rc, lc\n",
    "            if lc == -1:\n",
    "                v = rc\n",
    "                ret |= 1 << i\n",
    "                continue\n",
    "            if self._size[lc] <= index:\n",
    "                index -= self._size[lc]\n",
    "                v = rc\n",
    "                ret |= 1 << i\n",
    "            else:\n",
    "                v = lc\n",
    "        return ret\n",
    "\n",
    "    def minimum(self) -> int:\n",
    "        return self.at(0)\n",
    "\n",
    "    def maximum(self) -> int:\n",
    "        return self.at(-1)\n",
    "\n",
    "    def xorAll(self, x: int) -> None:\n",
    "        self._lazy ^= x\n",
    "\n",
    "    def __iter__(self):\n",
    "        q = [(0, 0)]\n",
    "        for i in range(self._maxLog - 1, -1, -1):\n",
    "            left = (self._lazy >> i) & 1\n",
    "            nq = []\n",
    "            for v, x in q:\n",
    "                lc = self._edges[2 * v]\n",
    "                rc = self._edges[2 * v + 1]\n",
    "                if left == 1:\n",
    "                    lc, rc = rc, lc\n",
    "                if lc != -1:\n",
    "                    nq.append((lc, 2 * x))\n",
    "                if rc != -1:\n",
    "                    nq.append((rc, 2 * x + 1))\n",
    "            q = nq\n",
    "        for v, x in q:\n",
    "            for _ in range(self._endCount[v]):\n",
    "                yield x\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        prefix = \"BinaryTrie(\"\n",
    "        content = list(map(str, self))\n",
    "        suffix = \")\"\n",
    "        if content:\n",
    "            content[0] = prefix + content[0]\n",
    "            content[-1] = content[-1] + suffix\n",
    "        else:\n",
    "            content = [prefix + suffix]\n",
    "        return \", \".join(content)\n",
    "\n",
    "    def __getitem__(self, k: int) -> int:\n",
    "        return self.at(k)\n",
    "\n",
    "    def __contains__(self, x: int) -> bool:\n",
    "        return not not self.count(x)\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return self._size[0]\n",
    "\n",
    "    def __bool__(self) -> bool:\n",
    "        return not not len(self)\n",
    "\n",
    "    def __ixor__(self, x: int) -> \"BinaryTrie\":\n",
    "        self.xorAll(x)\n",
    "        return self\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 2935. 找出强数对的最大异或值 II\n",
    "    # https://leetcode.cn/problems/maximum-strong-pair-xor-ii/\n",
    "    # 给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：\n",
    "    # |x - y| <= min(x, y)\n",
    "    # 你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。\n",
    "    # 返回数组 nums 所有可能的强数对中的 最大 异或值。\n",
    "    #\n",
    "    # 排序后，变为 y <= 2x\n",
    "    class Solution:\n",
    "        def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "            nums.sort()\n",
    "            res, left, n = 0, 0, len(nums)\n",
    "            trie = BinaryTrie(max=max(nums), addLimit=n, allowMultipleElements=True)\n",
    "            for right in range(n):\n",
    "                cur = nums[right]\n",
    "                trie.add(cur)\n",
    "                while left <= right and cur > 2 * nums[left]:\n",
    "                    trie.discard(nums[left])\n",
    "                    left += 1\n",
    "                trie.xorAll(cur)\n",
    "                res = max(res, trie.maximum())\n",
    "                trie.xorAll(cur)\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums) -> int:\n",
    "        tree = Node()\n",
    "        for num in nums:\n",
    "            node = tree\n",
    "            for i in range(21, -1, -1):\n",
    "                if (num >> i) & 1:\n",
    "                    if node.right:\n",
    "                        node = node.right\n",
    "                    else:\n",
    "                        node.right = Node()\n",
    "                        node = node.right\n",
    "                else:\n",
    "                    if node.left:\n",
    "                        node = node.left\n",
    "                    else:\n",
    "                        node.left = Node()\n",
    "                        node = node.left\n",
    "        self.max = 0\n",
    "        def dfs(node, num, flag, index, now_num):\n",
    "            if index == -1:\n",
    "                self.max = max(self.max, num ^ now_num)\n",
    "            else:\n",
    "                if flag == 2:\n",
    "                    if (num >> index) & 1:\n",
    "                        if node.left:\n",
    "                            next_num = now_num\n",
    "                            dfs(node.left, num, 2, index - 1, next_num)\n",
    "                        else:\n",
    "                            next_num = now_num | (1 << index)\n",
    "                            dfs(node.right, num, 2, index - 1, next_num)\n",
    "                    else:\n",
    "                        if node.right:\n",
    "                            next_num = now_num | (1 << index)\n",
    "                            dfs(node.right, num, 2, index - 1, next_num)\n",
    "                        else:\n",
    "                            next_num = now_num\n",
    "                            dfs(node.left, num, 2, index - 1, next_num)\n",
    "                if flag == 0:\n",
    "                    if index > 0:\n",
    "                        if (num >> (index - 1)) & 1:\n",
    "                            if (num >> index) & 1:\n",
    "                                if node.left:\n",
    "                                    next_num = now_num\n",
    "                                    dfs(node.left, num, 2, index - 1, next_num)\n",
    "                                else:\n",
    "                                    next_num = now_num | (1 << index)\n",
    "                                    dfs(node.right, num, 0, index - 1, next_num)\n",
    "                            else:\n",
    "                                if node.left:\n",
    "                                    next_num = now_num\n",
    "                                    dfs(node.left, num, 2, index - 1, next_num)\n",
    "                                if node.right:\n",
    "                                    next_num = now_num | (1 << index)\n",
    "                                    dfs(node.right, num, 0, index - 1, next_num)\n",
    "                        else:\n",
    "                            if node.left:\n",
    "                                next_num = now_num\n",
    "                                dfs(node.left, num, 0, index - 1, next_num)\n",
    "                    else:\n",
    "                        if node.left:\n",
    "                            next_num = now_num\n",
    "                            dfs(node.left, num, 2, index - 1, next_num)\n",
    "                if flag == 1:\n",
    "                    if (num >> index) & 1:\n",
    "                        if node.right:\n",
    "                            next_num = now_num | (1 << index)\n",
    "                            dfs(node.right, num, 1, index - 1, next_num)\n",
    "                    else:\n",
    "                        if node.right:\n",
    "                            next_num = now_num | (1 << index)\n",
    "                            dfs(node.right, num, 2, index - 1, next_num)\n",
    "                        else:\n",
    "                            next_num = now_num\n",
    "                            dfs(node.left, num, 0, index - 1, next_num)\n",
    "        for num in nums:\n",
    "            index = len(bin(num)[2:])\n",
    "            node = tree\n",
    "            for i in range(21, index, -1):\n",
    "                node = node.left\n",
    "            \n",
    "            if node.right:\n",
    "                dfs(node.right, num, 0, index - 1, 1 << index)\n",
    "            dfs(node.left, num, 1, index - 1, 0)\n",
    "        return self.max\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:     \n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "      d = Counter()\n",
    "      nums.sort()\n",
    "      ans = 0\n",
    "      l = 0\n",
    "      bits = 21\n",
    "      for v in nums:\n",
    "        for i in range(bits):\n",
    "          d[(i, v >> i)] += 1\n",
    "        while nums[l] * 2 < v:\n",
    "          for i in range(bits):\n",
    "            d[(i, nums[l] >> i)] -= 1\n",
    "          l += 1\n",
    "        now = 0\n",
    "        for i in range(bits - 1, -1, -1):\n",
    "          ev = v >> i & 1 ^ 1\n",
    "          nxt = now << 1 | ev\n",
    "          if d[(i, nxt)]: now = nxt\n",
    "          else: now = nxt ^ 1\n",
    "        ans = max(ans, now ^ v)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    __slots__ = (\"children\", \"val\")\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children: List[Trie | None] = [None, None]\n",
    "        self.val = [0, 0]\n",
    "\n",
    "    def insert(self, x: int):\n",
    "        node = self\n",
    "        for i in range(30, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            if node.children[v] is None:\n",
    "                node.children[v] = Trie()\n",
    "            node.val[v] += 1\n",
    "            node = node.children[v]\n",
    "           \n",
    "    def dele(self, x: int):\n",
    "        node = self\n",
    "        for i in range(30, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            node.val[v] -= 1\n",
    "            if node.val[v] == 0:\n",
    "                node.children[v] = None\n",
    "                break\n",
    "            node = node.children[v]\n",
    "           \n",
    "            \n",
    "    def search(self, x: int) -> int:\n",
    "        node = self\n",
    "        ans = 0\n",
    "        for i in range(30, -1, -1):\n",
    "            v = x >> i & 1\n",
    "            if node.children[v ^ 1]:\n",
    "                ans |= 1 << i\n",
    "                node = node.children[v ^ 1]\n",
    "            else:\n",
    "                node = node.children[v]\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        h = []\n",
    "        trie = Trie()\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            while h and x > h[0] * 2:\n",
    "                tmp = heapq.heappop(h)\n",
    "                trie.dele(tmp)\n",
    "            trie.insert(x)\n",
    "            ans = max(ans, trie.search(x))\n",
    "            heapq.heappush(h, x)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryTrie:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.root = {}\n",
    "        self.n = n\n",
    "        self.lst = [2 ** i for i in range(n)][::-1]\n",
    "        self.d = {'1': '0', '0': '1'}\n",
    "\n",
    "    def num_to_string(self, num):\n",
    "        lst = list(bin(num)[2:])\n",
    "        return (self.n - len(lst)) * ['0'] + lst\n",
    "\n",
    "    def add(self, num):\n",
    "        cur = self.root\n",
    "        for letter in self.num_to_string(num):\n",
    "            if letter not in cur:\n",
    "                cur[letter] = {}\n",
    "            cur = cur[letter]\n",
    "\n",
    "    def remove(self, num):\n",
    "        cur = self.root\n",
    "        temp = []\n",
    "        for letter in self.num_to_string(num):\n",
    "            temp.append([cur, letter])\n",
    "            cur = cur[letter]\n",
    "        for d, l in reversed(temp):\n",
    "            d.pop(l)\n",
    "            if len(d.keys()) > 0:\n",
    "                break\n",
    "\n",
    "    def search(self, num):\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        for index, letter in enumerate(self.num_to_string(num)):\n",
    "            k = self.d[letter]\n",
    "            if k in cur:\n",
    "                ans += self.lst[index]\n",
    "                cur = cur[k]\n",
    "            else:\n",
    "                cur = cur[letter]\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        v = 0\n",
    "        nums = sorted(set(nums))\n",
    "        if len(nums) == 1:\n",
    "            return v\n",
    "        trie = BinaryTrie(20)\n",
    "        left = 0\n",
    "        trie.add(nums[0])\n",
    "        for right in range(1, len(nums)):\n",
    "            while nums[left] * 2 < nums[right]:\n",
    "                trie.remove(nums[left])\n",
    "                left += 1\n",
    "            if left < right:\n",
    "                v = max(v, trie.search(nums[right]))\n",
    "            trie.add(nums[right])\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, a) -> int:\n",
    "        n = len(a)\n",
    "        a.sort()\n",
    "        ans = 0\n",
    "        mp = defaultdict(int)\n",
    "\n",
    "        def add(t):\n",
    "            p = 0\n",
    "            mp[(0, 20)] += 1\n",
    "            for i in range(19, -1, -1):\n",
    "                if t & (1 << i) > 0:\n",
    "                    p += 1\n",
    "                mp[(p, i)] += 1\n",
    "                p <<= 1\n",
    "        \n",
    "        def isok(p, k):\n",
    "            return mp[(p, k)] > 0\n",
    "\n",
    "        def remove(t):\n",
    "            p = 0\n",
    "            mp[(0, 20)] -= 1\n",
    "            for i in range(19, -1, -1):\n",
    "                if t & (1 << i) > 0:\n",
    "                    p += 1\n",
    "                mp[(p, i)] -= 1\n",
    "                p <<= 1\n",
    "\n",
    "        idx = n - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while a[idx] > 2 * a[i]:\n",
    "                remove(a[idx])\n",
    "                idx -= 1\n",
    "            if not isok(0, 20):\n",
    "                add(a[i])\n",
    "                continue\n",
    "            t = 0\n",
    "            for k in range(20, -1, -1):\n",
    "                t <<= 1\n",
    "                flag = (a[i] & (1 << k)) > 0\n",
    "                if flag:\n",
    "                    if not isok(t, k):\n",
    "                        t += 1\n",
    "                else:\n",
    "                    if isok(t + 1, k):\n",
    "                        t += 1\n",
    "            ans = max(ans, a[i] ^ t)\n",
    "            add(a[i])\n",
    "        return ans\n",
    "    \n",
    "sol = Solution()\n",
    "res = sol.maximumStrongPairXor([500,520,2500,3000])\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.end = False\n",
    "        self.left_num = 0\n",
    "        self.right_num = 0\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = Node(-1)\n",
    "\n",
    "    def insert(self, num):\n",
    "        s = bin(num)[2:].zfill(20)\n",
    "        node = self.root\n",
    "\n",
    "        for b in s:\n",
    "            if b == '0':\n",
    "                if node.left is None:\n",
    "                    node.left = Node(b)\n",
    "                    node.left_num += 1\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    node.left_num += 1\n",
    "                    node = node.left\n",
    "            else:\n",
    "                if node.right is None:\n",
    "                    node.right = Node(b)\n",
    "                    node.right_num += 1\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node.right_num += 1\n",
    "                    node = node.right\n",
    "        node.end = True\n",
    "\n",
    "    def get_xor_max(self, num):\n",
    "        s = bin(num)[2:].zfill(20)\n",
    "        node = self.root\n",
    "\n",
    "        mx = 0\n",
    "        k = 20\n",
    "        for b in s:\n",
    "            k -= 1\n",
    "            if b == '0':\n",
    "                if node.right_num == 0 or node.right is None:\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    mx |= (1 << k)\n",
    "                    node = node.right\n",
    "            else:\n",
    "                if node.left_num == 0 or node.left is None:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    mx |= (1 << k)\n",
    "                    node = node.left\n",
    "\n",
    "        return mx\n",
    "\n",
    "    def delete(self, num):\n",
    "        s = bin(num)[2:].zfill(20)\n",
    "        node = self.root\n",
    "\n",
    "        for b in s:\n",
    "            if b == '0':\n",
    "                node.left_num -= 1\n",
    "                node = node.left\n",
    "            else:\n",
    "                node.right_num -= 1\n",
    "                node = node.right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        trie = Trie()\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i in range(0, n):\n",
    "            while j < n and nums[j] <= 2 * nums[i]:\n",
    "                trie.insert(nums[j])\n",
    "                j += 1\n",
    "            mx = trie.get_xor_max(nums[i])\n",
    "            ans = max(mx, ans)\n",
    "            trie.delete(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RadixTree:\n",
    "    def __init__(self):\n",
    "        self.val = None\n",
    "        self.d = [None, None] #0 , 1\n",
    "        self.cnt = 0\n",
    "\n",
    "    def insert(self, num, depth):\n",
    "        node = self\n",
    "        for p in range(depth - 1, -1, -1):\n",
    "            tmp = 1 if 1 << p & num else 0\n",
    "            if not node.d[tmp]:\n",
    "                node.d[tmp] = RadixTree()\n",
    "            node = node.d[tmp]\n",
    "            node.cnt += 1\n",
    "        node.val = num\n",
    "        \n",
    "    def delete(self, num, depth):\n",
    "        node = self\n",
    "        for p in range(depth - 1, -1, -1):\n",
    "            tmp = 1 if 1 << p & num else 0\n",
    "            if not node.d[tmp]: break\n",
    "            if node.d[tmp].cnt == 1:\n",
    "                node.d[tmp] = None\n",
    "                break\n",
    "            node = node.d[tmp]\n",
    "            node.cnt -= 1\n",
    "\n",
    "    def maxXOR(self, num, depth) -> int:\n",
    "        node = self\n",
    "        res = 0\n",
    "        for p in range(depth - 1, -1, -1):\n",
    "            tmp = 1 if 1 << p & num else 0\n",
    "            if node.d[~tmp]:\n",
    "                node = node.d[~tmp]\n",
    "                res += 1 << p\n",
    "            else:\n",
    "                node = node.d[tmp]\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        # |x - y| <= min(x, y)  =>  y - x <= x  =>  y <= 2 * x\n",
    "        # 可删除01树\n",
    "        t = RadixTree()\n",
    "        l = 0\n",
    "        n = len(nums)\n",
    "        depth = 21\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            t.insert(nums[r], depth)\n",
    "            while nums[l] * 2 < nums[r]:\n",
    "                t.delete(nums[l], depth)\n",
    "                l += 1\n",
    "            res = max(res, t.maxXOR(nums[r], depth))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieBit:\n",
    "    def __init__(self, n=20):\n",
    "        \"\"\"template of add and remove num for maximum xor query\"\"\"\n",
    "        self.dct = dict()\n",
    "        self.n = n\n",
    "        return\n",
    "\n",
    "    def update(self, num):\n",
    "        cur = self.dct\n",
    "        for i in range(self.n, -1, -1):\n",
    "            w = 1 if num & (1 << i) else 0\n",
    "            if w not in cur:\n",
    "                cur[w] = dict()\n",
    "            cur = cur[w]\n",
    "            cur[\"cnt\"] = cur.get(\"cnt\", 0) + 1\n",
    "        return\n",
    "\n",
    "    def query(self, num):\n",
    "        \"\"\"query maximum xor value\"\"\"\n",
    "        cur = self.dct\n",
    "        ans = 0\n",
    "        for i in range(self.n, -1, -1):\n",
    "            w = 1 if num & (1 << i) else 0\n",
    "            if 1 - w in cur:\n",
    "                cur = cur[1 - w]\n",
    "                ans |= 1 << i\n",
    "            else:\n",
    "                cur = cur[w]\n",
    "        return ans\n",
    "\n",
    "    def delete(self, num):\n",
    "        \"\"\"remove one num\"\"\"\n",
    "        cur = self.dct\n",
    "        for i in range(self.n, -1, -1):\n",
    "            w = 1 if num & (1 << i) else 0\n",
    "            if cur[w].get(\"cnt\", 0) == 1:\n",
    "                del cur[w]\n",
    "                break\n",
    "            cur = cur[w]\n",
    "            cur[\"cnt\"] -= 1\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        trie = TrieBit()\n",
    "        nums = sorted(set(nums))\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        for y in nums:\n",
    "            while q and q[0]*2<y:\n",
    "                x = q.popleft()\n",
    "                trie.delete(x)\n",
    "            trie.update(y)\n",
    "            q.append(y)\n",
    "            ans = max(ans,trie.query(y))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.left = None #0\n",
    "        self.right = None #1\n",
    "        self.mx = 0 #以该节点为根的子数中的最大值 \n",
    "\n",
    "class BTree:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def add(self,v,arr):\n",
    "        cur = self.root\n",
    "        cur.mx = max(cur.mx,v)\n",
    "        for a in arr:\n",
    "            if a==0:\n",
    "                if cur.left==None:\n",
    "                    cur.left = Node()\n",
    "                    cur.left.mx = v\n",
    "                    cur = cur.left\n",
    "                else:\n",
    "                    cur.left.mx = max(cur.left.mx,v)\n",
    "                    cur = cur.left\n",
    "            else:\n",
    "                if cur.right==None:\n",
    "                    cur.right = Node()\n",
    "                    cur.right.mx = v\n",
    "                    cur = cur.right\n",
    "                else:\n",
    "                    cur.right.mx = max(cur.right.mx,v)\n",
    "                    cur = cur.right\n",
    "\n",
    "    def find(self,v,arr):\n",
    "        ret = 0\n",
    "        v2 = v//2 #找出的数字必须大于v2\n",
    "        if v2*2==v:\n",
    "            v2 -= 1\n",
    "        cur = self.root\n",
    "        found1 = False\n",
    "        for a in arr:\n",
    "            if a==0:\n",
    "                if found1:\n",
    "                    if cur.right!=None and cur.right.mx>v2:\n",
    "                        ret <<= 1\n",
    "                        ret += 1\n",
    "                        cur = cur.right\n",
    "                    elif cur.left!=None and cur.left.mx>v2:\n",
    "                        ret <<= 1\n",
    "                        cur = cur.left\n",
    "                    else:\n",
    "                        return 0\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "            else:\n",
    "                if found1==False:\n",
    "                    found1 = True\n",
    "                if found1:\n",
    "                    if cur.left!=None and cur.left.mx>v2:\n",
    "                        ret <<= 1\n",
    "                        ret += 1\n",
    "                        cur = cur.left\n",
    "                    elif cur.right!=None and cur.right.mx>v2:\n",
    "                        ret <<= 1\n",
    "                        cur = cur.right\n",
    "                    else:\n",
    "                        return 0\n",
    "                else:\n",
    "                    cur = cur.left\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        bitnum = None\n",
    "        arr = []\n",
    "        for i in range(len(nums)):\n",
    "            n = nums[i]\n",
    "            narr = None\n",
    "            if i==0:\n",
    "                tmp = []\n",
    "                while n!=0:\n",
    "                    n,ys = divmod(n,2)\n",
    "                    tmp.append(ys)\n",
    "                bitnum = len(tmp)\n",
    "                narr = tmp[::-1]\n",
    "            else:\n",
    "                narr = [0]*bitnum\n",
    "                idx = -1\n",
    "                while n!=0:\n",
    "                    n,ys = divmod(n,2)\n",
    "                    narr[idx] = ys\n",
    "                    idx -= 1\n",
    "            arr.append([nums[i],narr])\n",
    "\n",
    "        #print(arr)\n",
    "\n",
    "        tree = BTree()\n",
    "\n",
    "        for a in arr:\n",
    "            tree.add(a[0],a[1])\n",
    "\n",
    "        #print(tree.root.mx,tree.root.left.mx,tree.root.right.mx)\n",
    "\n",
    "        ret = 0\n",
    "        for a in arr:\n",
    "            tmp = tree.find(a[0],a[1])\n",
    "            ret = max(ret,tmp)\n",
    "\n",
    "        return ret\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        MAX = 1 << 21 - 1\n",
    "\n",
    "        Trie = lambda: defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "\n",
    "        def add(num):\n",
    "            mask = MAX\n",
    "            p = trie\n",
    "            while mask:\n",
    "                p = p[mask & num]\n",
    "                mask >>= 1\n",
    "            p[True] = num\n",
    "\n",
    "        def delete(p, mask, num):\n",
    "            if mask == 0:\n",
    "                del p[True]\n",
    "                return p\n",
    "            bit = mask & num\n",
    "            if not delete(p[bit], mask >> 1, num):\n",
    "                del p[bit]\n",
    "            return p\n",
    "\n",
    "        def get_partner(num):\n",
    "            mask = MAX\n",
    "            p = trie\n",
    "            while mask:\n",
    "                bit = num & mask\n",
    "                if bit ^ mask in p:\n",
    "                    p = p[bit ^ mask]\n",
    "                else:\n",
    "                    p = p[bit]\n",
    "                mask >>= 1\n",
    "            assert True in p\n",
    "            return p[True]\n",
    "\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        twice_i = 0\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            while twice_i < len(nums) and nums[twice_i] <= 2 * num:\n",
    "                add(nums[twice_i])\n",
    "                twice_i += 1\n",
    "            res = max(res, num ^ get_partner(num))\n",
    "            delete(trie, MAX, num)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        trie = {}\n",
    "        def add(x):\n",
    "            cur = trie\n",
    "            for i in range(19, -1, -1):\n",
    "                bit = (x >> i) & 1\n",
    "                if bit not in cur:\n",
    "                    cur[bit] = [{}, 1]\n",
    "                else:\n",
    "                    cur[bit][1] += 1\n",
    "                cur = cur[bit][0]\n",
    "        def remove(x):\n",
    "            cur = trie\n",
    "            for i in range(19, -1, -1):\n",
    "                bit = (x >> i) & 1\n",
    "                if cur[bit][1] == 1:\n",
    "                    cur.pop(bit)\n",
    "                    return\n",
    "                cur[bit][1] -= 1\n",
    "                cur = cur[bit][0]\n",
    "        def search(x):\n",
    "            cur = trie\n",
    "            ret = 0\n",
    "            for i in range(19, -1, -1):\n",
    "                bit = (x >> i) & 1\n",
    "                if bit ^ 1 in cur:\n",
    "                    ret |= (1 << i)\n",
    "                    cur = cur[bit ^ 1][0]\n",
    "                elif bit in cur:\n",
    "                    cur = cur[bit][0]\n",
    "                else:\n",
    "                    break\n",
    "            return ret\n",
    "        ans = p = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            while p < len(nums) and nums[p] * 2 < nums[i]:\n",
    "                remove(nums[p])\n",
    "                p += 1\n",
    "            add(nums[i])\n",
    "            ans = max(ans, search(nums[i]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0\n",
    "\n",
    "class Trie:\n",
    "    HIGH_BIT = 19\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def insert(self, val):\n",
    "        cur = self.root\n",
    "        for k in range(Trie.HIGH_BIT, -1, -1):\n",
    "\n",
    "            bit = (val >> k) & 1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            # 放后面是有必要的\n",
    "            cur.cnt += 1\n",
    "\n",
    "    # 这里是没考虑val不在树中的情况的（题目中也不会出现）\n",
    "    def remove(self, val):\n",
    "        cur = self.root \n",
    "        for k in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> k) & 1\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt -= 1\n",
    "\n",
    "\n",
    "    def search(self, tar_val):\n",
    "        res = 0\n",
    "        cur = self.root\n",
    "        for k in range(Trie.HIGH_BIT, -1, -1):\n",
    "            tarbit = ((tar_val >> k) & 1) ^ 1\n",
    "            if cur.children[tarbit] and cur.children[tarbit].cnt > 0:\n",
    "                res += 1 << k\n",
    "                cur = cur.children[tarbit]\n",
    "            else:\n",
    "                cur = cur.children[tarbit^1]\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = left = 0\n",
    "        tree = Trie()\n",
    "        for y in nums:\n",
    "            tree.insert(y)\n",
    "\n",
    "            while nums[left] * 2 < y:\n",
    "                tree.remove(nums[left])\n",
    "                left += 1\n",
    "            temp = tree.search(y)\n",
    "            ans = max(ans, temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    # __slots__ = 'children', 'cnt'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0  # 子树大小\n",
    "\n",
    "class Trie:\n",
    "    HIGH_BIT = 19\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    # 添加 val\n",
    "    def insert(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt += 1  # 维护子树大小\n",
    "        return cur\n",
    "\n",
    "    # 删除 val，但不删除节点\n",
    "    # 要求 val 必须在 trie 中\n",
    "    def remove(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            cur = cur.children[(val >> i) & 1]\n",
    "            cur.cnt -= 1  # 维护子树大小\n",
    "        return cur\n",
    "\n",
    "    # 返回 val 与 trie 中一个元素的最大异或和\n",
    "    # 要求 trie 中至少有一个元素\n",
    "    def max_xor(self, val: int) -> int:\n",
    "        cur = self.root\n",
    "        ans = 0\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            # 如果 cur.children[bit^1].cnt == 0，视作空节点\n",
    "            if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:\n",
    "                ans |= 1 << i\n",
    "                bit ^= 1\n",
    "            cur = cur.children[bit]\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        t = Trie()\n",
    "        ans = left = 0\n",
    "        for y in nums:\n",
    "            t.insert(y)\n",
    "            while nums[left] * 2 < y:\n",
    "                t.remove(nums[left])\n",
    "                left += 1\n",
    "            ans = max(ans, t.max_xor(y))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, a: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b=[f\"{n:022b}\" for n in a]\n",
    "        root={}\n",
    "        def insert(n):\n",
    "            r=root\n",
    "            for i in n:\n",
    "                if i not in r:\n",
    "                    r[i]=[{},1]\n",
    "                else:\n",
    "                    r[i][1]+=1\n",
    "                r=r[i][0]\n",
    "        def erase(r,n,i):\n",
    "            if i>=len(n):\n",
    "                return\n",
    "            erase(r[n[i]][0],n,i+1)\n",
    "            r[n[i]][1]-=1\n",
    "            if r[n[i]][1]==0:\n",
    "                del r[n[i]]\n",
    "        j=ans=0\n",
    "        for i in range(len(a)):\n",
    "            if i>0:\n",
    "                erase(root,b[i-1],0)\n",
    "            j=max(i,j)\n",
    "            while j<len(a) and a[i]*2>=a[j]:\n",
    "                insert(b[j])\n",
    "                j+=1\n",
    "            res=0\n",
    "            r=root\n",
    "            for s in b[i]:\n",
    "                k='0' if s=='1' else '1'\n",
    "                if k in r:\n",
    "                    res=res*2+1\n",
    "                    r=r[k][0]\n",
    "                else:\n",
    "                    res*=2\n",
    "                    r=r[s][0]\n",
    "            # print(i,j,ans,res,root)\n",
    "            ans=max(ans,res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.count = 0\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def addValue(self, value):\n",
    "        \"\"\" 向字典树中添加一个值 \"\"\"\n",
    "        node = self.root\n",
    "        for k in range(20, -1, -1):\n",
    "            bit = (value >> k) & 1\n",
    "            if not node.children[bit]:\n",
    "                node.children[bit] = TrieNode()\n",
    "            node = node.children[bit]\n",
    "            node.count += 1\n",
    "\n",
    "    def removeValue(self, value):\n",
    "        \"\"\" 从字典树中移除一个值 \"\"\"\n",
    "        node = self.root\n",
    "        for k in range(20, -1, -1):\n",
    "            bit = (value >> k) & 1\n",
    "            node = node.children[bit]\n",
    "            node.count -= 1\n",
    "\n",
    "    def findMaxXor(self, value):\n",
    "        \"\"\" 在字典树中寻找与给定值异或后最大的值 \"\"\"\n",
    "        node = self.root\n",
    "        maxXor = 0\n",
    "        for k in range(20, -1, -1):\n",
    "            bit = (value >> k) & 1\n",
    "            desired = 1 - bit\n",
    "            if node.children[desired] and node.children[desired].count > 0:\n",
    "                maxXor |= (1 << k)\n",
    "                node = node.children[desired]\n",
    "            elif node.children[bit]:\n",
    "                node = node.children[bit]\n",
    "            else:\n",
    "                break  # 如果没有合适的路径，提前结束循环\n",
    "        return maxXor\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        trie = Trie()\n",
    "        sorted_values = sorted(set(nums))\n",
    "        max_xor = 0\n",
    "        left, right = 0, 0\n",
    "        n = len(sorted_values)\n",
    "\n",
    "        while left < n:\n",
    "            while right < n and sorted_values[right] * 2 < sorted_values[left]:\n",
    "                trie.removeValue(sorted_values[right])\n",
    "                right += 1\n",
    "            max_xor = max(max_xor, trie.findMaxXor(sorted_values[left]))\n",
    "            trie.addValue(sorted_values[left])\n",
    "            left += 1\n",
    "\n",
    "        return max_xor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    \"\"\"字典树\n",
    "\n",
    "    Attributes:\n",
    "        1. size：包含的word总数\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        # key=0对应的value为前缀词数；key=1对应的value为词数\n",
    "        self._root = {0: 0, 1: 0}\n",
    "\n",
    "    @property\n",
    "    def size(self):\n",
    "        return self._root[0]\n",
    "\n",
    "    def add(self, word):\n",
    "        \"\"\"将word添加进字典树\n",
    "\n",
    "        Time Complexity:\n",
    "            O(len(word))\n",
    "\n",
    "        \"\"\"\n",
    "        t = self._root\n",
    "        t[0] += 1\n",
    "        for ch in word:\n",
    "            if not ch in t:\n",
    "                t[ch] = {0: 0, 1: 0}\n",
    "            t = t[ch]\n",
    "            t[0] += 1\n",
    "        t[1] += 1\n",
    "\n",
    "    def find(self, word):\n",
    "        \"\"\"查询word前缀词数和完全匹配词数\n",
    "\n",
    "        Returns:\n",
    "            1. 以word作为前缀的词数\n",
    "            2. 完全匹配word的词数\n",
    "\n",
    "        Time Complexity:\n",
    "            O(len(word))\n",
    "\n",
    "        \"\"\"\n",
    "        t = self._root\n",
    "        for ch in word:\n",
    "            if not ch in t:\n",
    "                return 0, 0\n",
    "            t = t[ch]\n",
    "        return t[0], t[1]\n",
    "\n",
    "    def remove(self, word):\n",
    "        \"\"\"将word从字典树中移除\n",
    "\n",
    "        Returns:\n",
    "            是否成功移除\n",
    "\n",
    "        Time Complexity:\n",
    "            O(len(word))\n",
    "\n",
    "        \"\"\"\n",
    "        if self.find(word)[1] == 0:\n",
    "            return False\n",
    "        t = self._root\n",
    "        t[0] -= 1\n",
    "        for ch in word:\n",
    "            t = t[ch]\n",
    "            t[0] -= 1\n",
    "        t[1] -= 1\n",
    "        return True\n",
    "\n",
    "    def query(self, word):\n",
    "        ans = 0\n",
    "        t = self._root\n",
    "        for k, ch in enumerate(word):\n",
    "            rch = '0' if ch == '1' else '1'\n",
    "            if rch in t and t[rch][0] > 0:\n",
    "                ans |= 1 << (20 - k)\n",
    "                t = t[rch]\n",
    "            elif ch in t and t[ch][0] > 0:\n",
    "                t = t[ch]\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, a) -> int:\n",
    "        n = len(a)\n",
    "        a.sort()\n",
    "        lt = ['0' * (21 - len(bin(v)[2:])) + bin(v)[2:] for v in a]\n",
    "        ans = 0\n",
    "        trie = Trie()\n",
    "\n",
    "        idx = n - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while a[idx] > 2 * a[i]:\n",
    "                trie.remove(lt[idx])\n",
    "                idx -= 1\n",
    "            ans = max(ans, trie.query(lt[i]))\n",
    "            trie.add(lt[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums = sorted(list(set(nums)))\n",
    "        n = len(nums)\n",
    "        L = 21\n",
    "        precals = [1<<i for i in range(L)][::-1]\n",
    "        def _getbit(v):\n",
    "            out = []\n",
    "            b = 1\n",
    "            for _ in range(L):\n",
    "                out.append(1 if b&v else 0)\n",
    "                b <<= 1\n",
    "            return out[::-1]\n",
    "        root = {}\n",
    "        maxone = 0\n",
    "        q = deque()\n",
    "        for v in nums:\n",
    "            while q and q[0][0]<v/2:\n",
    "                todel,bit = q.popleft()\n",
    "                now = root\n",
    "                st = []\n",
    "                for i in range(L):\n",
    "                    st.append(now)\n",
    "                    b = bit[i]\n",
    "                    now = now[b]\n",
    "                for i in range(L-1,-1,-1):\n",
    "                    b = bit[i]\n",
    "                    now = st[i]\n",
    "                    if i == L-1:\n",
    "                        del now[b]\n",
    "                    elif not now[b]:\n",
    "                        del now[b]\n",
    "                    else:\n",
    "                        break\n",
    "            bit = _getbit(v)\n",
    "            now = root\n",
    "            nowv = 0\n",
    "            for i in range(L):\n",
    "                b = bit[i]\n",
    "                if 1-b in now:\n",
    "                    now = now[1-b]\n",
    "                    nowv |= precals[i]\n",
    "                elif b in now:\n",
    "                    now = now[b]\n",
    "                else:\n",
    "                    break\n",
    "            maxone = max(maxone,nowv)\n",
    "            now =root\n",
    "            for i in range(L):\n",
    "                b = bit[i]\n",
    "                if b not in now:\n",
    "                    now[b] = {}\n",
    "                now = now[b]\n",
    "            now[-1] = 1\n",
    "            q.append([v,bit])\n",
    "            \n",
    "        return maxone"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "\n",
    "        root = {}\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def t(i):\n",
    "            l = [0]*20\n",
    "            idx = 19\n",
    "            while i:\n",
    "                if i&1:\n",
    "                    l[idx]=1\n",
    "                i>>=1\n",
    "                idx-=1\n",
    "            return l\n",
    "\n",
    "        def put(l):\n",
    "            i = 0\n",
    "            n = len(l)\n",
    "            node = root\n",
    "            while i<n:\n",
    "                if l[i] not in node:\n",
    "                    node[l[i]]=defaultdict(int)\n",
    "                node = node[l[i]]\n",
    "                node['#']+=1\n",
    "                i+=1\n",
    "\n",
    "        def delete(l):\n",
    "            i = 0\n",
    "            n = len(l)\n",
    "            node = root\n",
    "            while i<n:\n",
    "                if l[i] not in node:\n",
    "                    break\n",
    "                node[l[i]]['#']-=1\n",
    "                if node[l[i]]['#']==0:\n",
    "                    del node[l[i]]\n",
    "                    break\n",
    "                node = node[l[i]]\n",
    "                i+=1\n",
    "\n",
    "        \n",
    "        def get(l):\n",
    "            ans = 0\n",
    "            n = len(l)\n",
    "            idx = n-1\n",
    "            node = root\n",
    "            i = 0\n",
    "            while idx>=0:\n",
    "                if l[i]^1 in node:\n",
    "                    node = node[l[i]^1]\n",
    "                    ans+=2**idx\n",
    "                elif l[i] in node:\n",
    "                    node = node[l[i]]\n",
    "                else:\n",
    "                    break\n",
    "                idx-=1\n",
    "                i+=1\n",
    "            return ans\n",
    "\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        \n",
    "        i = 0\n",
    "\n",
    "        res = 0\n",
    "        for k in nums:\n",
    "            put(t(k))\n",
    "            while i<n and nums[i]*2<k:\n",
    "                delete(t(nums[i]))\n",
    "                i+=1\n",
    "            res = max(res, get(t(k)))\n",
    "        \n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.vs = []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        def floor(vs, t):\n",
    "            l, r = 0, len(vs)-1\n",
    "            while l < r:\n",
    "                mid = l+(r-l)//2\n",
    "                if vs[mid] < t:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid\n",
    "            if vs[l] < t:\n",
    "                return -1\n",
    "            return l\n",
    "\n",
    "        nums.sort()\n",
    "        root = TreeNode()\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i > 0:\n",
    "                node, t = root, nums[i]//2+(nums[i]&1)\n",
    "                cur = 0\n",
    "                k = floor(node.vs, t)\n",
    "                if k >= 0:\n",
    "                    for j in range(20, -1, -1):\n",
    "                        if nums[i]&(1<<j):\n",
    "                            if node.right is not None:\n",
    "                                k = floor(node.right.vs, t)\n",
    "                                if k >= 0:\n",
    "                                    cur += 1<<j\n",
    "                                    node = node.right\n",
    "                                else:\n",
    "                                    node = node.left\n",
    "                            else:\n",
    "                                node = node.left\n",
    "                        else:\n",
    "                            if node.left is not None:\n",
    "                                k = floor(node.left.vs, t)\n",
    "                                if k >= 0:\n",
    "                                    cur += 1<<j\n",
    "                                    node = node.left\n",
    "                                else:\n",
    "                                    node = node.right\n",
    "                            else:\n",
    "                                node = node.right\n",
    "                ans = max(ans, cur)\n",
    "\n",
    "            node = root\n",
    "            node.vs.append(nums[i])\n",
    "            for j in range(20, -1, -1):\n",
    "                if nums[i]&(1<<j):\n",
    "                    if node.left is None:\n",
    "                        node.left = TreeNode()\n",
    "                    node = node.left\n",
    "                else:\n",
    "                    if node.right is None:\n",
    "                        node.right = TreeNode()\n",
    "                    node = node.right\n",
    "                node.vs.append(nums[i])\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.count = 0\n",
    "        self.kids = [None, None]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        bits = [[0] * 20 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            temp = nums[i]\n",
    "            for j in range(20):\n",
    "                bits[i][j] = temp % 2\n",
    "                temp //= 2\n",
    "        right = 0\n",
    "        trie = Trie()\n",
    "        max_xor = 0\n",
    "        for i in range(n):\n",
    "            while right < n and nums[right] <= 2 * nums[i]:\n",
    "                temp = trie\n",
    "                temp.count += 1\n",
    "                for j in range(19, -1, -1):\n",
    "                    b = bits[right][j]\n",
    "                    if temp.kids[b] is None:\n",
    "                        temp.kids[b] = Trie()\n",
    "                    temp = temp.kids[b]\n",
    "                    temp.count += 1\n",
    "                right += 1\n",
    "            temp = trie\n",
    "            temp_xor = 0\n",
    "            bit_val = 2**19\n",
    "            for j in range(19, -1, -1):\n",
    "                b = bits[i][j]\n",
    "                if temp.kids[1 - b] is not None and temp.kids[1 - b].count > 0:\n",
    "                    temp_xor += bit_val\n",
    "                    temp = temp.kids[1 - b]\n",
    "                else:\n",
    "                    temp = temp.kids[b]\n",
    "                bit_val //= 2\n",
    "            max_xor = max(max_xor, temp_xor)\n",
    "            temp = trie\n",
    "            temp.count -= 1\n",
    "            for j in range(19, -1, -1):\n",
    "                b = bits[i][j]\n",
    "                temp = temp.kids[b]\n",
    "                temp.count -= 1\n",
    "        return max_xor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.count = 0\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, num: int) -> None:\n",
    "        node = self.root\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if bit not in node.children:\n",
    "                node.children[bit] = TrieNode()\n",
    "            node = node.children[bit]\n",
    "            node.count += 1\n",
    "\n",
    "    def delete(self, num: int) -> None:\n",
    "        node = self.root\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if bit in node.children:\n",
    "                if node.children[bit].count == 1:\n",
    "                    del node.children[bit]\n",
    "                    return\n",
    "                node = node.children[bit]\n",
    "                node.count -= 1\n",
    "\n",
    "    def find_max_xor(self, num):\n",
    "        node = self.root\n",
    "        xor_result = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if 1 - bit in node.children:\n",
    "                xor_result |= 1 << i\n",
    "                node = node.children[1 - bit]\n",
    "            else:\n",
    "                node = node.children[bit]\n",
    "        return xor_result\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        trie = Trie()\n",
    "        res = 0\n",
    "        l = 0\n",
    "        n = len(nums)\n",
    "        for r in range(n):\n",
    "            trie.insert(nums[r])\n",
    "            while l <= r and not 2 * nums[l] >= nums[r]:\n",
    "                trie.delete(nums[l])\n",
    "                l += 1\n",
    "            res = max(res, trie.find_max_xor(nums[r]))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "    children: {}\n",
    "    precount: int\n",
    "    count: int\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.precount = 0\n",
    "        self.count = 0\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    root: TrieNode\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def convert(self, d):\n",
    "        N1 = 20\n",
    "\n",
    "        res = [0] * N1\n",
    "        i = N1 - 1\n",
    "        while d:\n",
    "            res[i] = d % 2\n",
    "            i -= 1\n",
    "            d //= 2\n",
    "        return res\n",
    "\n",
    "    def add(self, val):\n",
    "        val = self.convert(val)\n",
    "        cur = self.root\n",
    "        for p in val:\n",
    "            if p not in cur.children:\n",
    "                cur.children[p] = TrieNode()\n",
    "            cur = cur.children[p]\n",
    "            cur.precount += 1\n",
    "        cur.count += 1\n",
    "\n",
    "    def remove(self, val):\n",
    "        val = self.convert(val)\n",
    "        if not self.exist(val):\n",
    "            return\n",
    "        cur = self.root\n",
    "        for p in val:\n",
    "            cur.children[p].precount -= 1\n",
    "            if cur.children[p].precount == 0:\n",
    "                del cur.children[p]\n",
    "                return\n",
    "            cur = cur.children[p]\n",
    "        cur.count -= 1\n",
    "\n",
    "    def exist(self, val):\n",
    "        cur = self.root\n",
    "        for p in val:\n",
    "            if p not in cur.children:\n",
    "                return False\n",
    "            cur = cur.children[p]\n",
    "        return cur.count > 0\n",
    "\n",
    "    def search(self, val):\n",
    "        val = self.convert(val)\n",
    "        cur = self.root\n",
    "        res = 0\n",
    "        for p in val:\n",
    "            res <<= 1\n",
    "            p1 = int(not p)\n",
    "            if p1 in cur.children:\n",
    "                res += 1\n",
    "                cur = cur.children[p1]\n",
    "            elif p in cur.children:\n",
    "                res += 0\n",
    "                cur = cur.children[p]\n",
    "        return res\n",
    "\n",
    "    def print(self):\n",
    "        res = []\n",
    "\n",
    "        def iter(cur, path):\n",
    "            if len(cur.children) == 0:\n",
    "                res.append(str(path))\n",
    "                return\n",
    "            for k in cur.children.keys():\n",
    "                iter(cur.children[k], path + str(k))\n",
    "\n",
    "        iter(self.root, path=\"\")\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        trie = Trie()\n",
    "        res = 0\n",
    "        left = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            while left < i and nums[left] < (num +1 ) // 2:\n",
    "                trie.remove(nums[left])\n",
    "                left += 1\n",
    "            trie.add(num)\n",
    "            # print(trie.print())\n",
    "            res = max(res, trie.search(num))\n",
    "            # print(num, res)\n",
    "        # print(trie.print())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = [None,None]\n",
    "        self.mx = 0\n",
    "        self.numbers = []\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, num):\n",
    "        node = self.root\n",
    "        for i in range(25, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            if node.children[bit] is None:\n",
    "                node.children[bit] = TrieNode()\n",
    "            node = node.children[bit]\n",
    "            node.mx = max(node.mx, num)\n",
    "            if i==0:\n",
    "                node.numbers.append(num)\n",
    "\n",
    "    def find_max_xor(self, num, lb):\n",
    "        node = self.root\n",
    "        syn = 0\n",
    "        lim = True\n",
    "        for i in range(25, -1, -1):\n",
    "            bit = (num >> i) & 1\n",
    "            rbit = 1 - bit\n",
    "            if node.children[rbit] is not None and node.children[rbit].mx>=lb:\n",
    "                selbit = rbit\n",
    "            elif node.children[bit] is not None and node.children[bit].mx>=lb:\n",
    "                selbit = bit\n",
    "            else:\n",
    "                return 0\n",
    "            node = node.children[selbit]\n",
    "            syn |= (selbit << i)\n",
    "            if lim and selbit != ((lb >> i) & 1):\n",
    "                lim = False\n",
    "            if i==0:\n",
    "                return num^syn\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        trie = Trie()\n",
    "        max_xor = 0\n",
    "        nums.sort()\n",
    "        for num in nums:\n",
    "            t=(num>>1) + 1 if (num&1) else num>>1\n",
    "            xor = trie.find_max_xor(num, t)\n",
    "            max_xor = max(max_xor, xor)\n",
    "            trie.insert(num)\n",
    "\n",
    "        return max_xor\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        m = nums[-1].bit_length()\n",
    "        t = {}\n",
    "        child = defaultdict(int)\n",
    "        \n",
    "        def addnode(x):\n",
    "            n = x.bit_length()\n",
    "            r = m - n\n",
    "            now = t\n",
    "            c = ''\n",
    "            st = '0' * r + bin(x)[2:]\n",
    "            for ch in st:\n",
    "                c += ch\n",
    "                child[c] += 1\n",
    "                v = int(ch)\n",
    "                if v not in now:\n",
    "                    now[v] = {}\n",
    "                now = now[v]    \n",
    "            \n",
    "        def delnode(x):\n",
    "            n = x.bit_length()\n",
    "            r = m - n\n",
    "            now = t\n",
    "            flag = True\n",
    "            c = ''\n",
    "            st = '0' * r + bin(x)[2:]\n",
    "            for ch in st:\n",
    "                c += ch\n",
    "                child[c] -= 1\n",
    "                if flag:\n",
    "                    v = int(ch)\n",
    "                    if child[c] == 0:\n",
    "                        now.pop(v)\n",
    "                        flag = False\n",
    "                    else:\n",
    "                        now = now[v]\n",
    "        \n",
    "        def getval(x):\n",
    "            n = x.bit_length()\n",
    "            r = m - n\n",
    "            st = '0' * r + bin(x)[2:]\n",
    "            now = t\n",
    "            if len(now) == 0: return 0\n",
    "            ans = 0\n",
    "            for ch in st:\n",
    "                ans *= 2\n",
    "                v = int(ch)\n",
    "                if (1-v) in now:\n",
    "                    now = now[1-v]\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    now = now[v]\n",
    "            return ans\n",
    "    \n",
    "        ans = 0\n",
    "        l = 0\n",
    "        addnode(nums[0])\n",
    "        for i in range(1, len(nums)):\n",
    "            while l < i and nums[l] * 2 < nums[i]:\n",
    "                delnode(nums[l])\n",
    "                l += 1\n",
    "            ans = max(ans, getval(nums[i]))\n",
    "            addnode(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.count = [0, 0]\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def addNumber(self, node: Node, deepth: int, number: int) -> None:\n",
    "        while deepth != -1:\n",
    "            num = (number >> deepth) & 1\n",
    "            if node.children[num] is None:\n",
    "                node.children[num] = Node()\n",
    "            node.count[num] += 1\n",
    "            node = node.children[num]\n",
    "            deepth -= 1\n",
    "\n",
    "    def removeNumber(self, node: Node, deepth: int, number: int) -> None:\n",
    "        while deepth != -1:\n",
    "            num = (number >> deepth) & 1\n",
    "            node.count[num] -= 1\n",
    "            node = node.children[num]\n",
    "            deepth -= 1\n",
    "\n",
    "    def queryNumber(self, node: Node, deepth: int, number: int) -> int:\n",
    "        res = 0\n",
    "        while deepth != -1:\n",
    "            num = (number >> deepth) & 1\n",
    "            if node.children[num] and node.count[num] > 0:\n",
    "                res |= (num << deepth)\n",
    "                node = node.children[num]\n",
    "            else:\n",
    "                res |= ((num ^ 1) << deepth)\n",
    "                node = node.children[num ^ 1]\n",
    "            deepth -= 1\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        highBit = nums[-1].bit_length()\n",
    "        maxNum = (1 << highBit) - 1\n",
    "        highBit -= 1\n",
    "        tree = Tree()\n",
    "        n = len(nums)\n",
    "        l, r = 0, 0\n",
    "        res = 0\n",
    "        while r < n:\n",
    "            while l <= r and r < n and nums[r] <= nums[l] * 2:\n",
    "                tree.addNumber(tree.root, highBit, nums[r])\n",
    "                res = max(res, tree.queryNumber(tree.root, highBit, nums[r] ^ maxNum) ^ nums[r])\n",
    "                r += 1\n",
    "            if r == n:\n",
    "                break\n",
    "            while nums[l] * 2 < nums[r]:\n",
    "                tree.removeNumber(tree.root, highBit, nums[l])\n",
    "                l += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict,deque\n",
    "from functools import cache\n",
    "import heapq\n",
    "from heapq import heappop,heappush \n",
    "from sortedcontainers import SortedDict,SortedList\n",
    "\n",
    "import math\n",
    "\n",
    "from math import inf\n",
    "\n",
    "class node:\n",
    "    __slots__ =\"child\",\"max\",\"min\",\"is_end\",\"cnt\"\n",
    "    def __init__(self) -> None:\n",
    "        self.child ={}\n",
    "        self.max =-inf\n",
    "        self.min = inf\n",
    "        self.is_end = False\n",
    "        self.cnt =0\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.root = node()\n",
    "    \n",
    "    def insert(self,w):\n",
    "        ls = '{:032b}'.format(w)\n",
    "        r = self.root\n",
    "        for i in ls:\n",
    "            i = int(i)\n",
    "            if i not in r.child:\n",
    "                r.child[i] = node()\n",
    "            r = r.child[i]\n",
    "            r.cnt +=1\n",
    "        #r.max = max(r.max,w)\n",
    "        #r.min = min(r.min,w)\n",
    "        r.is_end = True\n",
    "    \n",
    "    def remove(self,w):\n",
    "        ls = '{:032b}'.format(w)\n",
    "        r = self.root\n",
    "        for i in ls:\n",
    "            i = int(i)\n",
    "            r = r.child[i]\n",
    "            r.cnt -=1\n",
    "        #r.max = max(r.max,w)\n",
    "        #r.min = min(r.min,w)\n",
    "        r.is_end = True\n",
    "    \n",
    "    def get(self,x):\n",
    "        r =self.root\n",
    "        if len(r.child) == 0:\n",
    "            return -1\n",
    "        ls = '{:032b}'.format(x)\n",
    "        #print(ls,len(ls),x)\n",
    "        acc =0\n",
    "        for idx,i in enumerate( ls):\n",
    "            i = int(i)\n",
    "            #print(i,r.child)\n",
    "            if 1-i  in r.child and r.child[1-i].cnt >0:\n",
    "                acc += 1<<(31-idx)\n",
    "                #print(31-idx,acc)\n",
    "                #print(acc,x,1<<(31-idx),31-idx,1-i)\n",
    "                r= r.child[1-i]\n",
    "            elif i  in r.child:\n",
    "                r = r.child[i]\n",
    "            else:\n",
    "                break\n",
    "        return acc\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        nums.sort()\n",
    "        st=deque([])\n",
    "        tt = Trie()\n",
    "        for a in nums:\n",
    "            tt.insert(a)\n",
    "            st.append(a)\n",
    "            while st and st[0]*2 < a:\n",
    "                b =st[0]\n",
    "                tt.remove(b)\n",
    "                st.popleft()\n",
    "                #print(b,a)\n",
    "            ret =max(ret, tt.get(a))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.nxt = [None,None]\n",
    "        self.cnt = [0,0]\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums = sorted(list(set(nums)))\n",
    "        root = Node()\n",
    "        def add(v):\n",
    "            cur = root\n",
    "            for i in range(19,-1,-1):\n",
    "                if v >> i & 1:\n",
    "                    if cur.nxt[1] == None:\n",
    "                        cur.nxt[1] = Node()\n",
    "                    cur.cnt[1] += 1\n",
    "                    cur = cur.nxt[1]\n",
    "                else:\n",
    "                    if cur.nxt[0] == None:\n",
    "                        cur.nxt[0] = Node()\n",
    "                    cur.cnt[0] += 1\n",
    "                    cur = cur.nxt[0]\n",
    "            return\n",
    "        \n",
    "        def delete(v):\n",
    "            cur = root\n",
    "            for i in range(19,-1,-1):\n",
    "                flag = v >> i & 1\n",
    "                cur.cnt[flag] -= 1\n",
    "                cur = cur.nxt[flag]\n",
    "            return \n",
    "        \n",
    "        def xor(v):\n",
    "            cur = root;ans = 0\n",
    "            i = 19\n",
    "            for i in range(19,-1,-1):\n",
    "                if not cur:break\n",
    "                if v >> i & 1:\n",
    "                    if cur.cnt[0]:\n",
    "                        ans += 1<<i\n",
    "                        cur = cur.nxt[0]\n",
    "                    else:\n",
    "                        cur = cur.nxt[1]\n",
    "                else:\n",
    "                    if cur.cnt[1]:\n",
    "                        ans += 1<<i\n",
    "                        cur = cur.nxt[1]\n",
    "                    else:\n",
    "                        cur = cur.nxt[0]\n",
    "            return ans\n",
    "        \n",
    "        n = len(nums)\n",
    "        left = 0;res = 0 \n",
    "        for i in range(n):\n",
    "            while nums[left] * 2 < nums[i]:\n",
    "                delete(nums[left])\n",
    "                left += 1\n",
    "            res = max(res,xor(nums[i]))\n",
    "            add(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    __slots__ = [\"root\",\"count\"]\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "        self.count = [0] * 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        root = Trie()\n",
    "\n",
    "        def insert(x):\n",
    "            p = root\n",
    "            for i in range(20, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if 1 not in p.root:\n",
    "                        p.root[1] = Trie()\n",
    "                    p.count[1] += 1\n",
    "                    p = p.root[1]\n",
    "                else:\n",
    "                    if 0 not in p.root:\n",
    "                        p.root[0] = Trie()\n",
    "                    p.count[0] += 1\n",
    "                    p = p.root[0]\n",
    "\n",
    "        def remove(x):\n",
    "            p = root\n",
    "            for i in range(20, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    p.count[1] -= 1\n",
    "                    p = p.root[1]\n",
    "                else:\n",
    "                    p.count[0] -= 1\n",
    "                    p = p.root[0]\n",
    "\n",
    "        def query(x):\n",
    "            p = root\n",
    "            ans = 0\n",
    "            for i in range(20, -1, -1):\n",
    "                if x & (1 << i):\n",
    "                    if p.count[0]:\n",
    "                        ans += 1 << i\n",
    "                        p = p.root[0]\n",
    "                    else:\n",
    "                        if 1 not in p.root:\n",
    "                            p.root[1] = Trie()\n",
    "                        p = p.root[1]\n",
    "                else:\n",
    "                    if p.count[1]:\n",
    "                        ans += 1 << i\n",
    "                        p = p.root[1]\n",
    "                    else:\n",
    "                        if 0 not in p.root:\n",
    "                            p.root[0] = Trie()\n",
    "                        p = p.root[0]\n",
    "            return ans\n",
    "\n",
    "        n = len(nums)\n",
    "        j = n - 1\n",
    "        ans = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while j >= 0 and nums[j] - nums[i] > nums[i]:\n",
    "                remove(nums[j])\n",
    "                j -= 1\n",
    "            if j != i:\n",
    "                ans = max(ans, query(nums[i]))\n",
    "            insert(nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        #01Trie树\n",
    "        #滑动窗口内保存候选数字\n",
    "        #所有候选数字都存在trie树上\n",
    "        #当前数字x加入前 去除滑动窗口和trie树上不符合要求的数字\n",
    "        #当前数字x加入后，找到其最大异或值\n",
    "        class Trie:\n",
    "            def __init__(self):\n",
    "                self.tr = defaultdict(dict)\n",
    "                self.idx = 0\n",
    "                self.cnt = defaultdict(int) #cnt统计每个节点出现次数\n",
    "            def insert(self, s):\n",
    "                p = 0\n",
    "                for c in list(map(int, s)):\n",
    "                    if c not in self.tr[p]:\n",
    "                        self.idx += 1\n",
    "                        self.tr[p][c] = self.idx\n",
    "                    p = self.tr[p][c]\n",
    "                    self.cnt[p] += 1 #当前节点出现次数+1\n",
    "            def remove(self, s):\n",
    "                p = 0\n",
    "                for c in list(map(int, s)):\n",
    "                    p = self.tr[p][c]\n",
    "                    self.cnt[p] -= 1 #当前节点出现次数-1\n",
    "            def query(self, s):\n",
    "                p, res = 0, 0\n",
    "                for c in list(map(int, s)):\n",
    "                    #优先找与当前位不同的数字 若这样的节点存在且cnt>0 则走到该节点上\n",
    "                    if c ^ 1 in self.tr[p] and self.cnt[self.tr[p][c ^ 1]] > 0:\n",
    "                        p = self.tr[p][c ^ 1]\n",
    "                        res = res * 2 + (c ^ 1)\n",
    "                    else:\n",
    "                        p = self.tr[p][c]\n",
    "                        res = res * 2 + c\n",
    "                return res\n",
    "            \n",
    "        def get(x):\n",
    "            return bin(x)[2:].zfill(20)\n",
    "        nums.sort()\n",
    "        q = deque()\n",
    "        tr = Trie()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            while q and x - q[0] > q[0]:\n",
    "                tr.remove(get(q[0]))\n",
    "                q.popleft()\n",
    "            q.append(x)\n",
    "            tr.insert(get(x))\n",
    "            ans = max(ans, x ^ tr.query(get(x)))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumStrongPairXor(self, nums: List[int]) -> int:\n",
    "        class Trie:\n",
    "            def __init__(self):\n",
    "                self.tr = defaultdict(dict)\n",
    "                self.idx = 0\n",
    "                self.cnt = defaultdict(int)\n",
    "            def insert(self, s):\n",
    "                p = 0\n",
    "                for c in list(map(int, s)):\n",
    "                    if c not in self.tr[p]:\n",
    "                        self.idx += 1\n",
    "                        self.tr[p][c] = self.idx\n",
    "                    p = self.tr[p][c]\n",
    "                    self.cnt[p] += 1\n",
    "            def remove(self, s):\n",
    "                p = 0\n",
    "                for c in list(map(int, s)):\n",
    "                    p = self.tr[p][c]\n",
    "                    self.cnt[p] -= 1\n",
    "            def query(self, s):\n",
    "                p, res = 0, 0\n",
    "                for c in list(map(int, s)):\n",
    "                    if c ^ 1 in self.tr[p] and self.cnt[self.tr[p][c ^ 1]] > 0:\n",
    "                        p = self.tr[p][c ^ 1]\n",
    "                        res = res * 2 + (c ^ 1)\n",
    "                    else:\n",
    "                        p = self.tr[p][c]\n",
    "                        res = res * 2 + c\n",
    "                return res\n",
    "            \n",
    "        def get(x):\n",
    "            return bin(x)[2:].zfill(20)\n",
    "        nums.sort()\n",
    "        q = deque()\n",
    "        tr = Trie()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            while q and x - q[0] > q[0]:\n",
    "                tr.remove(get(q[0]))\n",
    "                q.popleft()\n",
    "            q.append(x)\n",
    "            tr.insert(get(x))\n",
    "            ans = max(ans, x ^ tr.query(get(x)))\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
